No.617 Nafmo Goes Shopping
Nafmo2
37zigenProblem Statement
Nafmo organized an event called CombNaf.
(CombNaf actually takes place on the day this problem is published. There will also be a Niconico Live broadcast.)
So he is going out to buy refreshments for the event.
At the store, he found $N$ items that looked good.
Each item has a weight $A_i$.
Nafmo can carry a total weight of at most $K$.
Nafmo usually chooses with cost performance in mind, but
this time he received $5000$ trillion yen from an oil magnate,
so he can buy things without worrying about the cost.
When Nafmo selects items so that the total weight is maximized within what he can carry,
output the total weight.
Note that Nafmo has little time left before CombNaf,
so he cannot go to the store, return to the venue, and then go back to the store once more.
(This means that he cannot make two round trips to carry $2K$.)
Input
$N \ K$ $A_1$ $A_2$ $\dots$ $A_N$
$1 \le N \le 20 $
$0 \le K \le 2 \times 10^6 $
$ 1 \le A_i \le 10^5$
Output
Output the total weight of the selected items.
Print a newline at the end.
Sample
Sample 1
Input
2 4 2 3
Output
3
Select nothing: 0
$A_1$: 2
$A_2$: 3
$A_1,A_2$: 5
Among these, the maximum that he can carry is 3, so output 3.
Sample 2
Input
4 4 1 2 3 5
Output
4
The maximum value 4 is attained when $i = 1,3$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。