/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 550 点
問題文
N 種類の品物があり、 i 種類目の品物の重みは w_i、価値は v_i です。どの種類の品物も 10^{10} 個ずつあります。
高橋君はこれから、品物をいくつか選んで、容量 W のバッグに入れます。高橋君は、選ぶ品物の価値を大きくしつつ、同じ種類の品物ばかりにならないようにしたいです。そこで高橋君は、i 種類目の品物を k_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
1 種類目の品物を 2 個、2 種類目の品物を 1 個選ぶと、うれしさの総和を 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
Score : 550 points
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