← 返回题目列表

AtCoder · tkppc2016_b

B. 重写

中文机器翻译题面 查看原题

問題文

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