分数: 366 分
问题陈述
高桥已经到了暑假的最后一天。只有 M 距离暑假结束还剩几分钟。
高桥有 N 作业剩下了。每份家庭作业 i (1 \leq i \leq N) 有固定的评估分数 R_i 完成后从老师处收到,所需时间为 T_i 分钟完成。
在这些期间 M 分钟,高桥可以选择一些家庭作业来完成。但是,以下条件适用:
- 每项家庭作业要么全部完成,要么根本不尝试。不可能部分完成作业。如果他努力的话,他必须花费 T_i 分钟完成它。
- 他不能多次完成同一个家庭作业。也就是说,每项作业最多只能完成一次。
- 所选家庭作业所需的总时间不得超过 M 分钟。
在这些条件下,高桥希望最大化已完成作业的总评估分数。
求高桥可以获得的最大总评价分数。
约束
- 1 \leq N \leq 100
- 1 \leq M \leq 10^5
- 1 \leq R_i \leq 10^9
- 1 \leq T_i \leq M
- 所有输入均为整数
输入
N M R_1 T_1 R_2 T_2 \vdots R_N T_N
- 第一行包含家庭作业的数量 N 以及距离暑假结束的剩余时间(以分钟为单位) M,用空格分隔。
- 的 i- 以下各项 N 行(1 \leq i \leq N) 包含评估分数 R_i 和所需时间 家庭作业的 T_i (以分钟为单位) i,用空格分隔。
输出
在一行上打印高桥可以获得的最大总评价分数。
示例输入 1
3 10 6 3 10 5 4 4
示例输出 1
16
示例输入 2
5 15 100 8 60 5 50 4 40 3 30 2
示例输出 2
190
示例输入 3
8 1000 1000000000 500 800000000 400 600000000 300 500000000 250 400000000 200 300000000 150 200000000 100 100000000 50
示例输出 3
2000000000