价值递减的背包

题目描述

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

高桥君要选择一些物品放入容量为 $W$ 的背包中。他想在避免选择过多同种物品的同时最大化所选物品的价值。因此，他定义选择 $k_i$ 个第 $i$ 种物品的幸福感为 $k_i v_i - k_i^2$。他想在总重量不超过 $W$ 的前提下，最大化所有种类幸福感的总和。计算他能达到的最大总幸福感。

输入格式

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

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

输出格式

输出答案。

样例

2 10
3 4
3 2

5

选择 $2$ 个第 $1$ 种物品和 $1$ 个第 $2$ 种物品时，总幸福感为 $5$，这是最优的。

这里，第 $1$ 种物品的幸福感为 $2 \times 4 - 2^2 = 4$，第 $2$ 种物品的幸福感为 $1 \times 2 - 1^2 = 1$。

总重量为 $9$，在容量 $10$ 以内。

3 6
1 4
2 3
2 7

14

1 10
1 7

12

数据范围

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