← 返回题目列表

AtCoder · abc373_f

I. 价值递减的背包

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

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