AT_arc073_b [ABC060D] Simple Knapsack

[problemUrl]: https://atcoder.jp/contests/abc060/tasks/arc073_b あなたは $ N $ 個の物と、強度 $ W $ のバッグを持っています。 $ i $ 個目の物は、重さが $ w_i $ で価値が $ v_i $ です。 あなたは、物のうちいくつかを選び、バッグに入れます。 ただし、選んだ物の重さの和は $ W $ 以下でなくてはいけません。 あなたは、バッグに入れた物の価値の総和を最大化したいです。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ W $ $ w_1 $ $ v_1 $ $ w_2 $ $ v_2 $ : $ w_N $ $ v_N $

価値の総和の最大値を出力する。

### 制約 - $ 1\ ≦\ N\ ≦\ 100 $ - $ 1\ ≦\ W\ ≦\ 10^9 $ - $ 1\ ≦\ w_i\ ≦\ 10^9 $ - すべての $ i\ =\ 2,3,...,N $ について、$ w_1\ ≦\ w_i\ ≦\ w_1\ +\ 3 $ - $ 1\ ≦\ v_i\ ≦\ 10^7 $ - $ W,\ w_i,\ v_i $ はすべて整数である ### Sample Explanation 1 $ 1,\ 3 $ 個目の物を選ぶと良いです。 ### Sample Explanation 2 $ 2,\ 4 $ 個目の物を選ぶと良いです。 ### Sample Explanation 3 すべての物が選べます。 ### Sample Explanation 4 $ 1 $ 個も物が選べません。