题目描述

Takahashi is at an all-you-can-eat restaurant.

The restaurant offers $N$ kinds of dishes. It takes $A_i$ minutes to eat the $i$-th dish, whose deliciousness is $B_i$.

The restaurant has the following rules:

• You can only order one dish at a time. The dish ordered will be immediately served and ready to eat.
• You cannot order the same kind of dish more than once.
• Until you finish eating the dish already served, you cannot order a new dish.
• After $T-0.5$ minutes from the first order, you can no longer place a new order, but you can continue eating the dish already served.

Let Takahashi's happiness be the sum of the deliciousness of the dishes he eats in this restaurant.

What is the maximum possible happiness achieved by making optimal choices?

高桥正在一家自助餐厅用餐。

餐厅提供 $N$ 种菜肴。吃完 $i$ 这道菜需要 $A_i$ 分钟，而这道菜的美味程度是 $B_i$ 。

餐厅有以下规定：

• 每次只能点一道菜。所点的菜肴将立即上桌并可以食用。
• 不能多次点同一种菜肴。
• 在您吃完已经上桌的菜肴之前，您不能再点新的菜肴。
• 从第一次点菜开始 $T-0.5$ 分钟后，您不能再点新菜，但可以继续享用已经上桌的菜肴。

高桥的幸福就是他在这家餐厅吃到的菜肴美味的总和。

做出最优选择后可能获得的最大幸福感是多少？

输入格式

输入内容按以下格式标准输入：

$N$ $T$
$A_1$ $B_1$
$:$
$A_N$ $B_N$

输出格式

打印高桥所能获得的最大幸福感。

样例 #1

样例输入 #1

2 60
10 10
100 100

样例输出 #1

110

样例 #2

样例输入 #2

3 60
10 10
10 20
10 30

样例输出 #2

60

样例 #3

样例输入 #3

3 60
30 10
30 20
30 30

样例输出 #3

50

样例 #4

样例输入 #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

说明

数据规模与约定

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

样例 $1$ 解释

按此顺序排列第一道菜和第二道菜，高桥的幸福感将是 $110$ 。

请注意，如果我们能及时点菜，那么我们可以花任意多的时间来吃这道菜。

样例 $2$ 解释

高桥可以在 $60$ 分钟内吃完所有菜肴。

样例 $3$ 解释

按照这个顺序点第二道和第三道菜，高桥的幸福感将是 $50$ 。

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