← 返回题目列表

AtCoder · abc145_e

E. 吃到饱

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

高桥在一家自助餐厅。

餐厅优惠 N 种菜。这需要 A_i 分钟吃的 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
:
A_N B_N

输出

打印出高桥能够获得的最大幸福。


示例输入 1

2 60
10 10
100 100

示例输出 1

110

按照这个顺序点第一道菜和第二道菜,高桥的幸福感将会是 110.

请注意,如果我们能够及时点菜,我们可以花任意时间来吃它。


示例输入 2

3 60
10 10
10 20
10 30

示例输出 2

60

高桥可以吃掉里面所有的菜 60 分钟。


示例输入 3

3 60
30 10
30 20
30 30

示例输出 3

50

按照这个顺序点第二道菜和第三道菜,高桥的幸福感将会是 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