AT_abc373_f [ABC373F] Knapsack with Diminishing Values

题目描述

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

高桥君现在要从这些物品中选择若干个，放入容量为 $W$ 的背包中。高桥君希望在尽量提高所选物品价值的同时，避免只选择同一种物品。因此，他将选择第 $i$ 种物品 $k_i$ 个时的快乐值定义为 $k_i v_i - k_i^2$。请在所选物品总重量不超过 $W$ 的前提下，选择物品使得所有种类的快乐值之和最大。求高桥君能够获得的最大快乐值。

输入格式

输入按以下格式从标准输入给出。

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

输出格式

请输出答案。

输入输出样例 #1

输入 #1

2 10
3 4
3 2

输出 #1

5

输入输出样例 #2

输入 #2

3 6
1 4
2 3
2 7

输出 #2

14

输入输出样例 #3

输入 #3

1 10
1 7

输出 #3

12

说明/提示

限制条件

• $1 \leq N \leq 3000$
• $1 \leq W \leq 3000$
• $1 \leq w_i \leq W$
• $1 \leq v_i \leq 10^9$
• 所有输入均为整数

样例解释 1

选择第 $1$ 种物品 $2$ 个，第 $2$ 种物品 $1$ 个，可以使快乐值总和达到 $5$，这是最优的。第 $1$ 种物品的快乐值为 $2 \times 4 - 2^2 = 4$，第 $2$ 种物品的快乐值为 $1 \times 2 - 1^2 = 1$。总重量为 $9$，可以放入容量为 $10$ 的背包中。

由 ChatGPT 4.1 翻译