题目描述

小可正在参加一项限时闯关挑战赛。比赛中共有 $N$ 个可选关卡，完成第 $i$ 个关卡需要连续操作 $A_i$ 分钟，成功后可获得 $B_i$ 点积分。

比赛规则如下：

• 每次只能选择一个关卡开始挑战，选定后立即开始计时操作。
• 每个关卡最多只能完成一次，不能重复挑战。
• 必须将当前正在进行的关卡彻底完成后，才能选择并开始下一个关卡。
• 从第一个关卡开始挑战的时刻算起，经过 $T-0.5$ 分钟后，挑战系统关闭，此时不能再开始新的关卡，但已经开始的关卡可以继续操作直至完成。

小可希望合理安排关卡的挑战顺序，使得最终获得的总积分最大。请你帮他算出这个最大积分。

输入格式

第一行两个整数 $N$ 和 $T$，表示可选关卡数量和闯关时限。

接下来 $N$ 行，每行 $2$ 个整数 $A_i,\ B_i$，分别表示第 $i$ 个关卡所需的操作时间和成功后可获得的积分。

输出格式

一个整数，表示可获得的最大总积分。

样例

2 60
10 10
100 100

110

3 60
10 10
10 20
10 30

60

3 60
30 10
30 20
30 30

50

10 100
15 23
20 18
13 17
24 12
18 29
19 27
23 21
18 20
27 15
22 25

145

样例1解释

依次挑战第 $1$ 个关卡和第 $2$ 个关卡。先挑战第 $1$ 个关卡，耗时 $10$ 分钟，获得 $10$ 分；此时已用去 $10$ 分钟，仍在 $T-0.5 = 59.5$ 分钟内，因此可以开始第 $2$ 个关卡。第 $2$ 个关卡耗时 $100$ 分钟，获得 $100$ 分。总积分为 $10 + 100 = 110$。请注意，虽然第 $2$ 个关卡的完成时间已超出 $T$，但只要开始时刻在时间限制内，就可以继续操作直至完成。

样例2解释

可以在 $60$ 分钟内完成所有三个关卡。例如依次挑战第 $1$、$2$、$3$ 个关卡，总耗时 $10+10+10=30$ 分钟，每个关卡的开始时刻都未超过 $59.5$ 分钟，总积分 $10+20+30=60$。

样例3解释

无论如何安排，最多只能挑战两个关卡。例如先挑战第 $2$ 个关卡（$30$ 分钟，$20$ 分），完成后时刻为 $30$；此时开始第 $3$ 个关卡（$30$ 分钟，$30$ 分），开始时刻 $30$ 仍在 $59.5$ 分钟内，总积分 $50$。若想挑战三个关卡，第三个关卡的开始时刻将为 $60$ 分钟，超过了 $59.5$ 的限制，因此无法开始。

数据范围

对于 $100\%$ 的数据，$2 \le N \le 3000$，$1 \le T \le 3000$，$1 \le A_i \le 3000$，$1 \le B_i \le 3000$。