All-you-can-eat

题目描述

Takahashi 在一家随便吃到饱的餐厅。 餐厅提供 $N$ 种菜。吃第 $i$ 种菜需要 $A_i$ 分钟，该菜的美味值是 $B_i$。 餐厅有以下规则：

你一次只能点一道菜。点的菜会立即上菜并且可以开始吃。 你不能重复点同一种菜。 在你吃完当前已经上桌的菜之前，不能再点新的菜。 从第一次点菜起 $T-0.5$ 分钟后，不能再下新的订单，但你可以继续吃已经上桌的菜。

让 Takahashi 的幸福值为他在这家餐厅吃到的菜的美味值之和。 通过最优选择能得到的最大幸福值是多少？

输入格式

输入按下述格式由标准输入提供： $N$ $T$ $A_1$ $B_1$ : $A_N$ $B_N$

输出格式

输出 Takahashi 能获得的最大可能幸福值。

2 60
10 10
100 100

110

3 60
10 10
10 20
10 30

60

3 60
30 10
30 20
30 30

50

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$ 输入中的所有数值都是整数。如果按第 1 道和第 2 道菜的这个顺序点菜，Takahashi 的幸福值将是 $110$。 注意，如果我们能及时点一道菜，我们可以花任意多的时间来吃它。
Takahashi 可以在 $60$ 分钟内吃完所有菜。
如果按第 2 道和第 3 道菜的这个顺序点菜，Takahashi 的幸福值将是 $50$。 无论我们以何种顺序，都不能点 3 道菜。

标签: AtCoder|abc145E

来源

AtCoder|abc145E