A dumbwaiter hoist can carry at most C kilograms in a single trip. There are n parcels waiting, each with a whole-number weight. You may load any subset of the parcels as long as their combined weight does not exceed C. Loading nothing gives a total of 0. Report the largest total weight you can load without exceeding the capacity.
Line 1: two integers n and C.
Line 2: n space-separated integers, the parcel weights.
A single integer: the maximum achievable total weight that is at most C.
Example 1
Input
4 10 3 5 4 6
Expected
10
Explanation
Choosing the parcels weighing 6 and 4 gives a total of 10, exactly the capacity, and no subset does better.
Example 2
Input
3 4 5 6 7
Expected
0
Explanation
Every parcel is heavier than the capacity of 4, so nothing can be loaded and the best total is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →