问题 CO: 吃菜
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：159
解决：41
题目描述
有n盘菜，每盘菜需要$a_i$的时间去吃，有$b_i$的美味度。
现在有如下规则：
现在有如下规则：
- 点了一盘菜之后，只能将其吃完后才能点下一盘菜。
- t 时刻过后就不能再点菜了，但是依旧可以吃菜。
- 每种菜只能点一次。
输入
n t
$a_1$ $b_1$
$a_2$ $b_2$
.....
$a_n$ $b_n$
2 <= n <= 3000 , 1 <= t <= 3000
1 <= $a_i$ , $b_i$ <= 3000
$a_1$ $b_1$
$a_2$ $b_2$
.....
$a_n$ $b_n$
2 <= n <= 3000 , 1 <= t <= 3000
1 <= $a_i$ , $b_i$ <= 3000
输出
最后能够得到的最大美味度是多少。
样例输入 复制
2 60
10 10
100 100
样例输出 复制
110
提示
按此顺序点第一道菜和第二道菜，最大美味度将达到110。
如果我们能及时点一道菜，我们可以花任何时间来吃它。
样例2
输入：
10 100
15 23
20 18
13 17
24 12
18 29
19 27
23 21
18 20
27 15
22 25
输出：
145
如果我们能及时点一道菜，我们可以花任何时间来吃它。
样例2
输入：
10 100
15 23
20 18
13 17
24 12
18 29
19 27
23 21
18 20
27 15
22 25
145