该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题目描述】

逛文创店的时候你想买一批周边放进自己的书包里，目前商店里面总共有 $N$ 种不同的文创商品。第 $i$ 种商品单件的重量是 $w_i$，单件带给你的初始快乐值是 $v_i$。商品的库存特别充足，相当于无限多。但是文创店有个特殊的优惠规则：

• 如果你买了 $k_i$ 件第 $i$ 种商品，你获得的总快乐值不是简单的 $k_i \times v_i$，而是会随着买的数量增多线性衰减，最终总快乐值公式定义为 $k_i \times v_i - k_i^2$。

书包的总容量是 $W$，所有选中商品的总重量不能超过背包容量。请求出你能获得的最大总快乐值。

【输入格式】

第一行两个正整数 $N,W$，分别代表商品的种类总数、书包的最大容量。 接下来 $N$ 行，每行两个整数 $w_i,v_i$，分别代表第 $i$ 种商品的单件重量和初始快乐值。

【输出格式】

输出一行一个整数，代表可以获得的最大总快乐值。

【样例 1】

2 10
3 4
3 2

5

【样例 1 解释】

第 $1$ 种商品买 $2$ 件获得快乐值 $2 \times 4 - 2^2 = 4$，第 $2$ 种商品买 $1$ 件获得快乐值 $1 \times 2 - 1^2 = 1$，总重量是 $3 \times 2 + 3 \times 1 = 9 \le 10$，总快乐值为 $5$，这是最优方案。

【样例 2】

3 6
1 4
2 3
2 7

14

【样例 2 解释】

最优方案可以凑到的最大总快乐值为 $14$。

【样例 3】

1 10
1 7

12

【样例 3 解释】

买 $3$ 件该商品，总快乐值是 $3 \times 7 - 3^2 = 12$，总重量 $3 \le 10$，这是最优选择。

【数据规模与约定】

对于全部的测试点，保证：

• $1 \le N \le 3000$
• $1 \le W \le 3000$
• $1 \le w_i \le W$，$1 \le v_i \le 10^9$