B - 書き換え（Rewrite） Editorial /

Time Limit: 1 sec / Memory Limit: 64 MB

問題文

joisinoお姉ちゃんの次の仕事は、書類の書き換えである。
書類はN個あり、それぞれに、重要度と、書き換えるのにかかる時間が決まっている。
joisinoお姉ちゃんはどうしても定時に帰りたいので、あと作業できる時間はMしかない。
そこでjoisinoお姉ちゃんは、時間内に書き換える書類の重要度の合計の最大化したいと思い、その最大値を求めるプログラムを作ることにした。

入力

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

N M
V_1 T_1
V_2 T_2
:
V_N T_N
  • 1行目には、書類の個数を表す整数N(1≦N≦500)と残っている時間M(1≦M≦500)が書かれている。
  • 続くN行のうちi行目には、i番目の書類の重要度V_i(1≦V_i≦10^5)と書き換えにかかる時間T_i(1≦T_i≦500)が書かれている。

出力

時間内に書き換えられる書類の重要度の合計の最大値を、1行に出力せよ。

入力例1

3 3
1 2
6 1
4 1

出力例1

10

2番目と3番目の書類を書き換える。

入力例2

10 10
92231 7
70370 1
4423 10
96481 4
69142 2
91784 3
16328 3
85936 8
93166 2
17394 1

出力例2

351801