問題文
Joisino Onee-chan的下一个工作是重写文档。
文件是N有几种类型,每种类型都有自己的重要性和重写所需的时间。
joisino Onee-chan 很想按时回家,所以她没有时间去工作。M只有一个。
因此,Joisino-neechan 希望在一段时间内最大化要重写的文档的总重要性,并决定创建一个程序来查找最大值。
入力
输入是按以下格式从标准输入给出的。
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
2th 和 由于您拿了第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