← 返回题目列表

AtCoder · awc0064_c

C. 暑期作业计划

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

分数: 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