問題一覧 > 通常問題

No.2492 Knapsack Problem?

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 227
作問者 : KumaTachiRenKumaTachiRen / テスター : hiro1729hiro1729
0 ProblemId : 9065 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-10-02 17:19:55

問題文

Alice はナップサックを買いにナップサック屋さんに来ました. ナップサック屋さんでは NN 個のナップサックが売られており,i (1iN)i\ (1\leq i\leq N) 個目のナップサックは容量 viv_i,重さ wiw_i です.

Alice はできるだけ容量が大きく,なおかつ重すぎないナップサックが欲しいと思っています.

重さ WW 以下のナップサックのうち容量が最大であるものの容量を求めてください. ただし重さ WW 以下のナップサックが存在しない場合は-1を出力してください.

入力

N WN\ W
v1 w1v_1\ w_1
v2 w2v_2\ w_2
\vdots
vN wNv_N\ w_N

  • 1N10001\leq N\leq 1000
  • 1W10001\leq W\leq 1000
  • 1vi10001\leq v_i\leq 1000
  • 1wi10001\leq w_i\leq 1000
  • 入力はすべて整数

出力

重さ WW 以下のナップサックが存在するならばそれらの中での容量の最大値を,存在しないならば-1を出力してください. 最後に改行してください.

サンプル

サンプル1
入力
3 7
6 9
3 3
5 6
出力
5

重さが 77 以下であるのは 2,32,3 個目のナップサックであり,それらの中での容積の最大値は 33 個目のナップサックの 55 です.

サンプル2
入力
3 14
1 59
2 65
3 58
出力
-1

重さが 1414 以下であるナップサックが存在しないので-1を出力してください.

サンプル3
入力
10 414
851 708
305 850
438 421
245 191
409 476
764 490
159 386
350 505
531 42
292 822
出力
531

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