问题描述

小k正在一家自助餐厅用餐。 餐厅提供$N$种不同的菜品。吃第$i$道菜需要花费$A_i$分钟，其美味度为$B_i$。 餐厅有以下规则：

• 一次只能点一道菜。所点的菜会立即上菜并可以开始食用。
• 同一种类的菜品不能重复点单。
• 在吃完已上菜的菜品之前，不能点新菜。
• 从第一次点单开始$T-0.5$分钟后，将无法再点新菜，但可以继续食用已上菜的菜品。 定义小k的幸福感为他在餐厅所吃菜品的美味度之和。 通过最优选择，小k能达到的最大幸福感是多少？

约束条件

• $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

输出

输出小k能达到的最大幸福感。

样例输入1

2 60
10 10
100 100

样例输出1

110

按顺序点第一道和第二道菜，小k的幸福感将为110。 注意，只要在规定时间内点单，就可以花费任意时间来食用该菜品。

样例输入2

3 60
10 10
10 20
10 30

样例输出2

60

小k可以在60分钟内吃完所有菜品。

样例输入3

3 60
30 10
30 20
30 30

样例输出3

50

按顺序点第二道和第三道菜，小k的幸福感将为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