题目描述

废了九牛二虎之力，徐老师终于把这位美丽的公主从恶龙手里救了出来，他想约公主去吃点好吃的，顺便给让公主开心一下。他知道公主最喜欢吃日料了，于是他们来到了一家名为“竹哩”的日料放题餐馆。（小知识：“放题”就是自助的意思，但和传统自助餐又有区别。客人落座后，食物即点即做，有条不紊地端到桌上） 这家日料店提供 $N$ 种菜品。吃第 $i$ 种菜需要 $A_i$ 分钟，其开心指数为 $B_i$。但是有以下点菜规则：

• 每次只能点一道菜。点的菜会立即送过来，可以马上吃。

• 不能重复点同一种菜。

• 在你吃完已经送到的菜之前，不能点新的菜。

• 从第一道菜下单开始算起的 $T-0.5$ 分钟后，不能再点新的菜，但你可以继续吃已经上菜的菜。

公主开不开心取决于在这家日料里吃到的菜的开心指数总和。

现在就让你帮徐老师算一下，在做出最优选择的情况下，公主能达到的最大开心指数是多少？

数据范围

$2 \leq N \leq 3000$ $1 \leq T \leq 3000$ $1 \leq A_i \leq 3000$ $1 \leq B_i \leq 3000$ 输入中的所有数值均为整数。

输入格式

从标准输入读入数据，具体格式如下： $N$ $T$ $A_1$ $B_1$ $\vdots$ $A_N$ $B_N$

输出格式

公主能达到的最大开心指数

样例输入

2 60
10 10
100 100

样例输出

110

按照这个顺序点第一道菜和第二道菜，公主的开心指数将达到 110。 需要注意的是，如果徐老师能及时点菜的话，可以花任意多的时间去把它吃掉。

样例输入

3 60
10 10
10 20
10 30

样例输出

60

公主可以在 60 分钟内吃完所有菜。

### 样例输入 ```input3 3 60 30 10 30 20 30 30 ``` ### 样例输出 ```output3 50 ``` 如果徐老师按照这个顺序点第二道菜和第三道菜，公主的**开心指数**将达到 50。 无论以哪种顺序点菜，徐老师都无法点三道菜。

样例输入

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

样例输出

145