← 返回题目列表

Codeforces · 542/F

F. 任务

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

坡旅甲正在寻找他的朋友。他已经做了n个任务,对于每个任务,男孩都会用整数qi评估它的有趣程度,以及完成任务所需的时间ti(以分钟为单位)。

他的任务的一个有趣的特点是:每个参与者都应该根据他的喜好获得最适合他的任务。该任务是根据包含一些问题的交互式测验来选择的。玩家应该用“是”或“否”回答这些问题。根据问题的答案,参与者要么转到另一个问题,要么转到任务中的一项任务。换句话说,任务是一棵二叉树,它的节点包含问题,叶子包含任务。

我们知道,任务玩家回答在获得任务之前提出的任何问题只需一分钟。波利卡普知道他的朋友们都很忙,他们参与任务的时间不能超过 T 分钟。 Polycarp 希望从他制作的 n 个任务中选择一些,为它们发明相应的一组问题,并用它们形成一个二叉树形式的交互式测验,这样无论玩家如何回答测验问题,他最多花费 T 分钟来完成整个任务(即回答所有问题并完成任务)。具体来说,任务可以包含零问题并直接进入任务。每个任务只能使用一次(即,对问题给出不同答案的人应该获得不同的任务)。

坡旅甲希望任务中涉及的任务的总“兴趣”值尽可能大。考虑到在任何回答问题的情况下任务都应在 T 分钟内完成,帮助他确定任务的最大可能总兴趣值。

输入

第一行包含两个整数 n 和 T (1 ≤ n ≤ 1000, 1 ≤ T ≤ 100) — Polycarp 所做的任务数量以及任务玩家应该适应的最长时间。

接下来的 n 行分别包含两个整数 ti、qi (1 ≤ ti ≤ T, 1 ≤ qi ≤ 1000) — 完成第 i 个任务所需的时间(以分钟为单位)及其兴趣值。

输出

打印一个整数 - 任务中所有任务的最大可能总兴趣值。

示例

输入 #1

5 5
1 1
1 1
2 2
3 3
4 4

输出 #1

11

输入 #2

5 5
4 1
4 2
4 3
4 4
4 5

输出 #2

9

输入 #3

2 2
1 1
2 10

输出 #3

10

注意

在第一个示例测试中,所有五个任务都可以用四个问题来补充并加入到一个任务中。

在第二个示例测试中,不可能使用所有五个任务,但您可以选择其中两个,即最有趣的任务。

在第三个示例测试中,最佳策略是仅将第二个任务包含到任务中。

这是说明示例测试答案的图片。蓝色圆圈代表问题,每个圆圈的两个箭头代表一个人根据他对该问题的回答而去的地方。任务是红色椭圆形。