#ABC485F. 大桥
大桥
大桥
题目描述
有 件物品 ,每件各一件。第 件物品的价格为 ,价值为 。
高桥每过一次桥,所有价格至少为 的物品的价格都会减少 。
对每个 ,求出下面这个值:在高桥过桥 次之后,选出零件或多件物品,使得它们的总价格不超过 时,所选物品总价值的最大值。
输入格式
输入第一行为两个整数 。
接下来 行,第 行为两个整数 。
输出格式
输出 行,共 个整数。第 行表示 时的答案。
3 4
1 3
2 5
4 8
8
16
16
16
16
样例 1 解释
时物品价格仍为初始价格,选择物品 ,总价值为 。
时所有物品价格减少 ,选择物品 ,总价格 ,总价值为 。
5 6
4 6
4 7
6 11
2 4
1 2
11
17
24
30
30
30
30
2 1
1 4
1 7
7
11
数据范围
对于所有测试数据,保证:
- ;
- ;
- ;
- 所有输入值均为整数。
子任务
本题共 20 个测试点,按测试点计分:
| 测试点 | 分值 | 每个测试点 | 特殊性质 |
|---|---|---|---|
| 且 | |||
| 且 | |||
| 无特殊限制 |
每个测试点单独评分,全部测试点的得分之和即为本题得分。
相关
在下列比赛中: