择优突围

G-14断裂带的金属地板上嵌着六个数据终端，每个终端都被沙尘埋了一半。终端外壳上的倒计时数字在跳动——有的还剩五小时，有的还剩三小时，有的只剩四十分钟。

"每个终端里都有我的碎片。"Echo的投影蹲下来——她做了一个蹲下的动作，虽然投影本身没有重量——"但回收每个碎片需要不同的时间。有的碎片大，要两小时；有的碎片小，只要二十分钟。"

CC用数据刀刮开第一个终端表面的沙尘："总共多少时间？"

"六小时。"你说，"猎杀者经过之前。"

"那就挑最划算的先拿。"CC说，"我在矿区捡破烂的时候，就是这么干的——时间紧，先拿单位时间里最值钱的。"

你打开终端，六个碎片的参数跳出来——价值和耗时。你开始掂量：同样的时间，哪个碎片能换回更多Echo的记忆。

"第一个，价值一百，时间二十分钟。"你说，"最划算。"

"拿。"CC已经撬开了终端外壳。

"第二个，价值八十，时间十五分钟。"

"拿。"

你一个个往下算，把最值钱的先塞进背包，累计时间逼近六小时。最后一个碎片价值很高，但要吃掉整整三小时——如果硬拿，猎杀者的脚步声就会和终端的嗡鸣重叠。

"放弃最后一个。"你说，"时间不够了。"

CC把五个碎片的数据晶片收进背包，金属肩膀在暗红的天光下反光："走。"

题目描述

有 $n$ 个任务，每个任务需要时间 $t_i$，获得价值 $v_i$。总时间不超过 $T$，求能获得的最大价值。

输入格式

$n, T$。然后 $n$ 行，每行 $t_i, v_i$。

输出格式

最大价值。

输入样例

1
5 1 49
8 2 1 7 9

输出样例

2

提示

• 按单位时间价值 $v_i/t_i$ 从高到低排序，优先选比值高的。
• 累计时间不能超过 $T$。
• 时间不够的任务跳过。

五个碎片的数据晶片在背包里轻轻碰撞，发出细碎的声响。Echo的投影走在你们中间，光晕比刚才稳定了一些——每回收一个碎片，她的信号就强一分。

"下一个终端在断裂带对面。"她说，"但那里有裂缝——空间被Zero撕成了碎片，直接走会掉进去。"

"那咋个办？"CC问。

"搭一条跳板路。"Echo说，"像爬楼梯——一次跨多级，比一级一级爬快得多。"

CC看了你一眼："你听得懂？"

"听得懂。"你说，"先找能一步跳到的最远安全点，然后从那里继续跳。"

"那走。"CC把数据刀插回腰间，"我来开路。"