No testdata at current.

题目描述

小Y今天冲去餐厅打卡“豪华限定大餐”，面前摆着 N道特色菜~

每道菜都有两个关键属性：

• 吃完第i道菜需要花费 $A_i$ 分钟
• 吃完这道菜能收获 $B_i$ 点快乐值

餐厅给的用餐时限是 T分钟，还出了个贴心规则：只要在T分钟之前开始吃最后一道菜，哪怕这道菜吃完的时间超了T分钟，也能让小Y把它吃完~

不过有个小限制：必须吃完一道菜，才能开始吃下一道哦！

现在需要帮小Y规划吃菜的顺序和选择，让他拿到最多的快乐值~

输入格式

第一行输入两个数$n$和$T$ 接下来$n$行
每行两个数分别为$a_i$和$b_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

145

数据规模

所有输入的数字小于等于3000