AT_abc145_e [ABC145E] All-you-can-eat

题目描述

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

有 $N$ 种不同的菜，第 $i$ 种菜需要 $A_i$ 分钟才能吃完，美味度为 $B_i$。

这家店的规则如下：

• 每次只能点一道菜。点菜后会立即上菜，可以立刻开始吃。
• 同一种菜不能点两次及以上。
• 必须吃完当前已上的菜后，才能点下一道菜。
• 从第一次点菜开始，$T-0.5$ 分钟之后就不能再点菜了，但已经上的菜可以继续吃完。

高桥君的满足度为本次用餐中所吃菜的美味度之和。

请问高桥君如果合理安排，最多能获得多少满足度？

输入格式

输入按以下格式从标准输入读入。

$N$ $T$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

输出格式

输出高桥君合理安排时能获得的最大满足度。

样例 1

输入

2 60
10 10
100 100

输出

110

样例 2

输入

3 60
10 10
10 20
10 30

输出

60

样例 3

输入

3 60
30 10
30 20
30 30

输出

50

样例 4

输入

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

依次点第 $1$ 道和第 $2$ 道菜，可以获得满足度 $110$。请注意，只要点菜时在时间限制内，吃完所需时间不受限制。

样例解释 2

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

样例解释 3

依次点第 $2$ 和第 $3$ 道菜，可以获得满足度 $50$。无论如何排序，都无法点 $3$ 道菜。

由 ChatGPT 4.1 翻译