分数: 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