Problem Statement

Tomorrow is Alice's birthday party. $N+1$ of Alice's friends, including Bob, will attend the party. Each participant brings one present for Alice. For the $N$ participants other than Bob, it is known that the $i$-th participant brings a present with weight $w_i$ and value $v_i$.

Since there is a limit to how much Alice can carry home, among the ways to choose presents such that the total weight is at most $W$, she chooses one that maximizes the total value. If there are multiple choices that maximize the total value, she randomly selects one of them.

Bob is planning to prepare a present with weight $X$. Bob does not want to spend much money on the present, but if Alice does not choose it, the money will be wasted, so he intends to make the value of his present the minimum value $V$ such that Alice is certain to choose it. Here, $V$ must be a positive integer. For each of the cases $X=~1,~2,~\cdots,~W$, find $V$ for Bob.

Input

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

All inputs are integers and satisfy the following constraints.

• $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$

Output

Output $W$ lines. On the $i$-th line, output the value of $V$ for $X=i$.

Sample

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