/
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 525 点
問題文
N 個の商品 1,2,\dots,N が 1 個ずつあります。 商品 i の料金は c_i で価値は v_i です。
高橋君が橋を 1 回渡るたびに、料金が 1 以上であるようなすべての商品の料金が 1 下がります。
j=0,1,\dots,M について、以下の値を求めてください。
- 高橋君が橋を j 回渡った後、料金の合計が M 以下になるように 0 個以上の商品を選ぶとき、選んだ商品の価値の合計としてあり得る最大値
制約
- 1 \leq N \leq 10^2
- 1 \leq c_i \leq M \leq 10^4
- 1 \leq v_i \leq 10^9
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M c_1 v_1 c_2 v_2 \vdots c_N v_N
出力
答えを合計 M+1 行で出力せよ。 k 行目には、j=k-1 のときの答えを出力せよ。
入力例 1
3 4 1 3 2 5 4 8
出力例 1
8 16 16 16 16
j=0 のとき、すべての商品の料金は最初のままです。商品 1,2 を選ぶと、価値の合計を 8 にすることができ、またこれがあり得る最大値です。
j=1 のとき、すべての商品の料金は 1 下がります。商品 1,2,3 を選ぶと、価値の合計を 16 にすることができ、またこれがあり得る最大値です。
入力例 2
5 6 4 6 4 7 6 11 2 4 1 2
出力例 2
11 17 24 30 30 30 30
入力例 3
2 1 1 4 1 7
出力例 3
7 11
Score : 525 points
Problem Statement
There are N items 1,2,\dots,N, one of each. Item i has a price of c_i and a value of v_i.
Each time Takahashi crosses a bridge, the price of every item whose price is at least 1 decreases by 1.
For each j=0,1,\dots,M, find the following value.
- The maximum possible total value of the chosen items when, after Takahashi has crossed the bridge j times, zero or more items are chosen so that their total price is at most M.
Constraints
- 1 \leq N \leq 10^2
- 1 \leq c_i \leq M \leq 10^4
- 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 M c_1 v_1 c_2 v_2 \vdots c_N v_N
Output
Print the answers in M+1 lines in total. The k-th line should contain the answer for j=k-1.
Sample Input 1
3 4 1 3 2 5 4 8
Sample Output 1
8 16 16 16 16
For j=0, the prices of all items remain as they were initially. Choosing items 1 and 2 makes the total value 8, which is the maximum possible.
For j=1, the prices of all items decrease by 1. Choosing items 1, 2, and 3 makes the total value 16, which is the maximum possible.
Sample Input 2
5 6 4 6 4 7 6 11 2 4 1 2
Sample Output 2
11 17 24 30 30 30 30
Sample Input 3
2 1 1 4 1 7
Sample Output 3
7 11