E - 自助餐

得分：500 分

题目描述

高桥在一家自助餐馆里。

这家餐馆提供 $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 分钟内吃完所有菜。

3 60
30 10
30 20
30 30

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