AT_abc373_f [ABC373F] Knapsack with Diminishing Values

[problemUrl]: https://atcoder.jp/contests/abc373/tasks/abc373_f $ 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 $ $ \vdots $ $ w_N $ $ v_N $

答えを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 3000 $ - $ 1\ \leq\ W\ \leq\ 3000 $ - $ 1\ \leq\ w_i\ \leq\ W $ - $ 1\ \leq\ v_i\ \leq\ 10^9 $ - 入力はすべて整数 ### Sample Explanation 1 $ 1 $ 種類目の品物を $ 2 $ 個、$ 2 $ 種類目の品物を $ 1 $ 個選ぶと、うれしさの総和を $ 5 $ にすることができ、これが最適です。 $ 1 $ 種類目の品物についてのうれしさは $ 2\ \times\ 4\ -\ 2^2\ =\ 4 $、$ 2 $ 種類目の品物についてのうれしさは $ 1\ \times\ 2\ -\ 1^2\ =\ 1 $ です。 また、重さの総和は $ 9 $ であり、容量 $ 10 $ のバッグに入ります。