坡旅甲正在寻找他的朋友。他已经做了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
注意
在第一个示例测试中,所有五个任务都可以用四个问题来补充并加入到一个任务中。
在第二个示例测试中,不可能使用所有五个任务,但您可以选择其中两个,即最有趣的任务。
在第三个示例测试中,最佳策略是仅将第二个任务包含到任务中。
这是说明示例测试答案的图片。蓝色圆圈代表问题,每个圆圈的两个箭头代表一个人根据他对该问题的回答而去的地方。任务是红色椭圆形。