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