B19 - Knapsack 2 Editorial /

Time Limit: 10 sec / Memory Limit: 1024 MB

配点: 1000 点

この問題は、Educational DP Contest E - Knapsack 2 と同じ問題です。

問題文

宝箱には N 個の品物が入っており、それぞれ 1 から N までの番号が付けられています。
品物 i の重さは w_i であり、価値は v_i です。

太郎君は、いくつかの品物を選んで持ち帰りたいと考えています。
しかし、彼のナップザックには容量制限があるので、重さの合計が W 以下になるようにする必要があります。
価値の合計としてあり得る最大の値はいくつですか。

制約

  • 1 \leq N \leq 100
  • 1 \leq W \leq 10^9
  • 1 \leq w_i \leq W
  • 1 \leq v_i \leq 1000
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。 

N W
w_1 v_1
w_2 v_2
 :
w_N v_N

出力

答えを整数で出力してください。

入力例 1

4 7
3 13
3 17
5 29
1 10

出力例 1

40

たとえば品物 1・品物 2・品物 4 を選んだ場合、価値の合計は 13+17+10=40 となります。
価値の合計を 41 以上にする方法は存在しません。

入力例 2

3 100
55 2
75 3
40 2

出力例 2

4

品物 1・品物 3 を選ぶのが最適です。

入力例 3

10 1000000000
80000000 99
11000000 119
12000000 150
15000000 174
16000000 168
18000000 190
19000000 187
25000000 273
28000000 307
30000000 319

出力例 3

1986