AT_abc032_d [ABC032D] ナップサック問題

[problemUrl]: https://atcoder.jp/contests/abc032/tasks/abc032_d 0/1ナップサック問題を解いてください。0/1ナップサック問題とは以下のような問題のことです。 - $ N $ 個の荷物があり、$ i\ (1≦i≦N) $ 番目の荷物には価値 $ v_i $ と重さ $ w_i $ が割り当てられている。 - 許容重量 $ W $ のナップサックが1つある。 - 重さの和が $ W $ 以下となるように荷物の集合を選びナップサックに詰め込むとき、価値の和の最大値を求めよ。ただし、同じ荷物は一度しか選ぶことができない。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ W $ $ v_1 $ $ w_1 $ $ v_2 $ $ w_2 $ : $ v_N $ $ w_N $ - $ 1 $ 行目には、荷物の数を表す整数 $ N\ (1≦N≦200) $ とナップサックの許容重量を表す整数 $ W(1≦W≦10^9) $ が空白区切りで与えられる。 - $ 2 $ 行目からの $ N $ 行には、各荷物の情報が与えられる。そのうち $ i(1≦i≦N) $ 行目には、$ i $ 番目の荷物の価値を表す整数 $ v_i\ (1≦v_i≦10^9) $ と重さを表す整数 $ w_i\ (1≦w_i≦10^9) $ が空白区切りで与えられる。 - 「$ N≦30 $」、「全ての$ i(1≦i≦N) $ について $ 1≦w_i≦1000 $」、「全ての$ i(1≦i≦N) $ について $ 1≦v_i≦1000 $」という $ 3 $ つの条件のうち少なくとも1つの条件が成り立つ。

出力は以下の形式で標準出力に行うこと。 $ 1 $ 行目に、達成できる最大の合計価値を出力せよ。末尾の改行を忘れないこと。

### 部分点 この問題には部分点が設定されている。満点は $ 100 $ 点である。 - $ N≦30 $ を満たすデータセット $ 1 $ に正解した場合は、$ 34 $ 点が与えられる。 - $ N≦200 $ かつ全ての $ i(1≦i≦N) $ について $ 1≦w_i≦1000 $ を満たすデータセット $ 2 $ に正解した場合は、上記の点数とは別に $ 33 $ 点が与えられる。 - $ N≦200 $ かつ全ての $ i(1≦i≦N) $ について $ 1≦v_i≦1000 $ を満たすデータセット $ 3 $ に正解した場合は、上記の点数とは別に $ 33 $ 点が与えられる。 ### Sample Explanation 1 $ 2 $ 番目と $ 3 $ 番目のアイテムを選ぶと、合計の重みが $ 10 $ で価値が $ 16 $ となり、最大価値を達成できます。 この入出力例は、データセット $ 1,2,3 $ の制約を満たしているため、全てのデータセットの採点に用いられます。 ### Sample Explanation 2 この入出力例は、データセット $ 1 $ の制約のみ満たしているため、データセット $ 2,3 $ の採点には用いられません。 ### Sample Explanation 3 この入出力例は、データセット $ 3 $ の制約を満たしていないため、データセット $ 3 $ の採点には用いられません。 ### Sample Explanation 4 この入出力例は、データセット $ 2 $ の制約を満たしていないため、データセット $ 2 $ の採点には用いられません。