103735: [Atcoder]ABC373 F - Knapsack with Diminishing Values

Problem Statement

There are $N$ types of items. The $i$-th type of item has a weight of $w_i$ and a value of $v_i$. Each type has $10^{10}$ items available.

Takahashi is going to choose some items and put them into a bag with capacity $W$. He wants to maximize the value of the selected items while avoiding choosing too many items of the same type. Hence, he defines the happiness of choosing $k_i$ items of type $i$ as $k_i v_i - k_i^2$. He wants to choose items to maximize the total happiness over all types while keeping the total weight at most $W$. Calculate the maximum total happiness he can achieve.

Constraints

• $1 \leq N \leq 3000$
• $1 \leq W \leq 3000$
• $1 \leq w_i \leq W$
• $1 \leq v_i \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $W$
$w_1$ $v_1$
$w_2$ $v_2$
$\vdots$
$w_N$ $v_N$

Output

Print the answer.

Sample Input 1

2 10
3 4
3 2

Sample Output 1

5

By choosing $2$ items of type $1$ and $1$ item of type $2$, the total happiness can be $5$, which is optimal.

Here, the happiness for type $1$ is $2 \times 4 - 2^2 = 4$, and the happiness for type $2$ is $1 \times 2 - 1^2 = 1$.

The total weight is $9$, which is within the capacity $10$.

Sample Input 2

3 6
1 4
2 3
2 7

Sample Output 2

14

Sample Input 3

1 10
1 7

Sample Output 3

12

问题陈述

有$N$种物品。第$i$种物品的重量为$w_i$，价值为$v_i$。每种物品都有$10^{10}$个可用。

高桥打算选择一些物品并将它们放入容量为$W$的背包中。他希望在选择的物品中最大化价值，同时避免选择太多同一类型的物品。因此，他定义选择$k_i$个第$i$种物品的幸福感为$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种物品的幸福感是$2 \times 4 - 2^2 = 4$，第2种物品的幸福感是$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