← 返回题目
题库练习 [ABC145E] All-you-can-eat
← 上一题 下一题 →

A7561 | [ABC145E] All-you-can-eat

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

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

有 $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
输出 #1
110
输入 #2
3 60
10 10
10 20
10 30
输出 #2
60
输入 #3
3 60
30 10
30 20
30 30
输出 #3
50
输入 #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
C++ 编辑器
输入
输出