Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Prepared by Ibrahim Mesecan.
Transporter
Shqip
Mr. Ardit has a shipping company. He transports the packages of other people from Tirana to Shkoder.
Because he is shipping packages of other people, he is not able to break apart the packages, and he
has to ship them as they have been given. His car can ship at most C kilograms,
thus he cannot always move all the packages at once. He has to choose some packages that best fits
to his car capacity. 
Question:
Write a program that is going to get the weights of n packages and choose the packages in such a way
that the total weights of selected packages is the highest and less than or equal to the given capacity C.
Input specification
First, you will be given two integers: the number of packages (n) and the amount (C) that his car can carry
where 1 ≤ n ≤ 12 and 1 < C ≤ 1000. Then, you will be given n integers which represent the
weights of the given packages. And, each of the package have at most 100Kgs.
Output specification
As the output, give a single integer which shows the highest amount that he can carry with his car.
Sample Input I
5 16
4 5 4 4 6
Sample Output I
15
|
Sample Input II
6 13
3 3 3 3 3 4
Sample Output II
13
|
Output Explanation :
Input 1: He can carry at most 15Kgs, when the packages 4, 5, and 6 are selected.
Input 2: If the packages 3, 3, 3, and 4 are selected, he can carry 13Kgs.
Для отправки решений необходимо выполнить вход.
|