自助餐

题目描述

高桥君来到了一家自助餐厅。

有 $N$ 种料理，第 $i$ 种料理需要 $A_i$ 分钟吃完，美味度为 $B_i$。

这家店的规则如下：

• 一次只能点 $1$ 份料理。点的料理会立即上桌，可以开始吃。
• 同一种料理不能点 $2$ 次以上。
• 在吃完已上桌的料理之前，不能点下一份料理。
• 从第一次点单算起 $T-0.5$ 分钟之后不能再点单，但可以继续吃已上桌的料理。

高桥君的满足度定义为这次就餐中他所吃的料理的美味度总和。

高桥君采取恰当行动时，满足度最大是多少呢？

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出高桥君采取恰当行动时满足度的最大值。

样例

2 60
10 10
100 100

110

按第 $1$ 种、第 $2$ 种的顺序点单，满足度可以达到 $110$。

注意只要点单能在时限内完成，吃多久都可以。

3 60
10 10
10 20
10 30

60

可以在 $60$ 分钟内吃完所有料理。

3 60
30 10
30 20
30 30

50

按第 $2$ 种、第 $3$ 种的顺序点单，可以将满足度提高到 $50$。

无论按什么顺序点单，都无法点 $3$ 份料理。

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

145

数据范围

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