A19 - Knapsack 1 Editorial /

Time Limit: 10 sec / Memory Limit: 1024 MB

配点: 1000 点

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

問題文

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

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

制約

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

入力

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

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

4 100
25 47
25 53
25 62
25 88

出力例 2

250

すべての品物を選ぶことができます。

入力例 3

10 285
29 8000
43 11000
47 10000
51 13000
52 16000
66 14000
72 25000
79 18000
82 23000
86 27000

出力例 3

87000