問題文

明日はAliceの誕生日パーティです。パーティにはBobを含めてAliceの友達が $N+1$ 人参加します。それぞれの参加者はAliceのためにプレゼントを1つずつ持ち寄りますが、Bobを除く $N$ 人について、 $i$ 番目の参加者は重さ $w_i$ 、価値 $v_i$ のプレゼントを持ち寄ることがわかっています。

Aliceは持ち帰ることのできる荷物の量に限界があるので、プレゼントの重さの総和が $W$ 以下になるような選び方のうち、価値の総和が最大になるような選び方をします。ただし、価値の総和が最大となるような選び方が複数ある場合、そのような選び方の1つをランダムに選択します。

Bobは重さが $X$ のプレゼントを用意しようとしています。Bobはプレゼントにあまりお金をかけたくありませんが、Aliceにプレゼントが選ばれないとお金が無駄になってしまうため、プレゼントの価値はAliceに確実に選ばれるような最小の価値 $V$ にしようと考えています。ただし、 $V$ は正整数である必要があります。 $X=~1,~2,~\cdots,~W$ のそれぞれの場合について、Bobのために $V$ を求めてあげてください。

入力

$N\ W$
$w_1~v_1$
$\vdots$
$w _N~v_N$

入力は全て整数で以下の制約を満たす。

• $1\leq N \leq 100$
• $1\leq W \leq 10^5$
• $1 \leq w_i \leq 10^5$
• $1 \leq v_i \leq 10^7$

出力

$W$ 行出力してください。 $i$ 行目には $X=i$ のときの $V$ の値を出力してください。

サンプル

3 5
1 2
2 3
3 5

2
4
6
7
9

3 5
10 10
10 100
100 100

1
1
1
1
1            

4 10
1 1
2 3
4 5
8 9

3
4
4
5
7
8
9
10
12
13