F - Big Bridge 解説 /

実行時間制限: 2 sec / メモリ制限: 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