問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 282
作問者 : 👑 Nafmo2Nafmo2 / テスター : 37zigen37zigen
5 ProblemId : 2021 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-10 20:23:27

問題文

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を取ります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。