AtCoder Beginner Contest 032

D - ナップサック問題


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 512MB

問題文

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つの条件が成り立つ。

部分点

この問題には部分点が設定されている。満点は 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 点が与えられる。

出力

出力は以下の形式で標準出力に行うこと。

1 行目に、達成できる最大の合計価値を出力せよ。末尾の改行を忘れないこと。


入力例1

3 10
15 9
10 6
6 4

出力例1

16

2 番目と 3 番目のアイテムを選ぶと、合計の重みが 10 で価値が 16 となり、最大価値を達成できます。 この入出力例は、データセット 1,2,3 の制約を満たしているため、全てのデータセットの採点に用いられます。


入力例2

30 499887702
128990795 137274936
575374246 989051853
471048785 85168425
640066776 856699603
819841327 611065509
704171581 22345022
536108301 678298936
119980848 616908153
117241527 28801762
325850062 478675378
623319578 706900574
998395208 738510039
475707585 135746508
863910036 599020879
340559411 738084616
122579234 545330137
696368935 86797589
665665204 592749599
958833732 401229830
371084424 523386474
463433600 5310725
210508742 907821957
685281136 565237085
619500108 730556272
88215377 310581512
558193168 136966252
475268130 132739489
303022740 12425915
122379996 137199296
304092766 23505143

出力例2

3673016420

この入出力例は、データセット 1 の制約のみ満たしているため、データセット 2,3 の採点には用いられません。


入力例3

10 2921
981421680 325
515936168 845
17309336 371
788067075 112
104855562 96
494541604 960
32007355 161
772339969 581
55112800 248
98577050 22

出力例3

3657162058

この入出力例は、データセット 3 の制約を満たしていないため、データセット 3 の採点には用いられません。


入力例4

10 936447862
854 810169801
691 957981784
294 687140254
333 932608409
832 42367415
642 727293784
139 870916042
101 685539955
853 243593312
369 977358410

出力例4

1686

この入出力例は、データセット 2 の制約を満たしていないため、データセット 2 の採点には用いられません。


Submit提出する