题目描述

Takahashi在一家自助餐厅用餐。

该餐厅提供$N$种菜品。吃完第$i$种菜需要$A_i$分钟，其美味程度为$B_i$。

该餐厅有以下规则：

• 一次只能点一个菜。点菜后，菜品将立即上桌并可以食用。
• 不能重复点同一种菜。
• 在吃完已上桌的菜之前，不能再点新菜。
• 第一道菜被点餐后的$T-0.5$分钟内可以继续点菜，但不能超过这个时间。

Takahashi的快乐度是他在这家餐厅里吃到的菜的美味程度之和。

通过做出最优选择，Takahashi能达到的最大快乐度是多少？

约束条件

• $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$ $:$ $A_N$ $B_N$

输出

打印Takahashi能达到的最大快乐度。

示例输入 1

2 60
10 10
100 100

示例输出 1

110

通过按照顺序点餐第一道和第二道菜，Takahashi的快乐度将达到$110$。

请注意，只要我们在规定时间内点菜，可以花费任意时间来吃菜。

示例输入 2

3 60
10 10
10 20
10 30

示例输出 2

60

Takahashi可以在$60$分钟内吃完所有的菜。

示例输入 3

3 60
30 10
30 20
30 30

示例输出 3

50

按照顺序点餐第二道和第三道菜，Takahashi的快乐度将达到$50$。

无论我们以什么顺序点菜，都不能点三道菜。

示例输入 4

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

示例输出 4

145