分数: 550 点
问题陈述
有 N 项目类型。的 i第一种物品的重量为 w_i 和值为 v_i。每种类型都有 10^{10} 项目可用。
高桥要挑选一些物品,放进一个有容量的袋子里 W。他希望最大化所选物品的价值,同时避免选择太多相同类型的物品。因此,他定义了 幸福 选择 k_i 类型的项目 i as k_i v_i - k_i^2。他希望选择的项目能够使所有类型的总幸福感最大化,同时保持总重量最多 W。计算他可以获得的最大总幸福感。
约束
- 1 \leq N \leq 3000
- 1 \leq W \leq 3000
- 1 \leq w_i \leq W
- 1 \leq v_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N W w_1 v_1 w_2 v_2 \vdots w_N v_N
输出
打印答案。
示例输入 1
2 10 3 4 3 2
示例输出 1
5
通过选择 2 类型的项目 1 和 1 类型项目 2,总的幸福感可以是 5,这是最佳的。
在这里,类型的幸福 1 is 2 \times 4 - 2^2 = 4,以及类型的幸福 2 is 1 \times 2 - 1^2 = 1.
总重量为 9,在容量范围内 10.
示例输入 2
3 6 1 4 2 3 2 7
示例输出 2
14
示例输入 3
1 10 1 7
示例输出 3
12