No.617 Nafmo、買い出しに行く

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 160
作問者 : Nafmo2Nafmo2 / テスター : 37zigen37zigen
1 ProblemId : 2021 / 出題時の順位表

問題文

Nafmo君は CombNaf というイベントを主催しました。
(公開当日にCombNafが実際にあります。ニコ生もやります)
そこで、イベントの差し入れを買いに行くことになりました。

店に行くと良さそうな$N$個の商品がありました。
それぞれに重さ $A_i$が設定されています
Nafmo君は$K$以下の重さであれば運ぶことができます。

Nafmo君は普段はコストパフォーマンスを考えて選びますが、
今回は石油王から $5000$兆円 をもらえたので
コストを考えずに買うことができるようになりました。

Nafmo君が、運べる範囲内で、重さの合計が最大になるように商品を選んだとき、
合計の重さを出力してください。
なお、Nafmo君にはCombNafまでに残された時間が少ないため、
店に行き、会場に戻り、もう一回、店に戻るということはできません。
(これはつまり2往復して$2K$運ぶ。ということができないことを指します。)

入力

$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$

出力

選んだ商品の重さの合計を出力してください。
最後に改行してください。

サンプル

サンプル1
入力
2 4
2
3
出力
3

選ばない:0
$A_1$:2
$A_2$:3
$A_1,A_2$:5
この中で運べる中の最大値は3なので3を出力します。

サンプル2
入力
4 4
1
2
3
5
出力
4


$i = 1,3$のとき、最大値4を取ります。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。