sk has $N$ beautiful boxes, numbered $1$ to $N$. The $i$-th box has two attributes, $S_i$ and $P_i$, representing its size and beauty, respectively. Box $i$ can be placed inside any box $j$ that satisfies $S_i \leq S_j$.

mxr's birthday is approaching, so sk plans to give mxr some boxes as a birthday gift. Since giving empty boxes doesn't sound very good, sk intends to put other boxes inside them. Specifically, sk plans to choose $K$ pairs of boxes, and for each pair, place one box inside the other (if two boxes have the same size, he can choose which one to put inside the other; otherwise, he puts the smaller box into the larger one). For each pair of boxes $(i, j)$, if box $i$ is inside box $j$, the beauty value of this pair is $P_j - P_i$, because sk feels that the beauty of the inner box is wasted.

Since unpacking boxes is a tedious task, mxr might not want too many pairs of boxes, and sk does not know what the ideal value of $K$ is. Therefore, for each $K$ from $1$ to $\lfloor \frac{N}{2} \rfloor$, you need to help sk find the maximum total beauty value he can obtain using at most $K$ pairs of boxes (i.e., the maximum sum of the beauty values of all box pairs).

Input

The first line contains an integer $N$.

The next $N$ lines each contain two integers representing $S_i$ and $P_i$.

Output

Output $\lfloor \frac{N}{2} \rfloor$ lines, where the $i$-th line represents the answer for $K = i$.

Examples

Input 1

5
1 4
1 5
1 3
3 4
3 1

Output 1

3
5

Constraints

For $10\%$ of the data, $N \leq 10$.

For $30\%$ of the data, $N \leq 100$.

For $60\%$ of the data, $N \leq 2 \times 10^3$.

For $100\%$ of the data, $1 \leq N \leq 2 \times 10^5$, $1 \leq S_i \leq N$, $1 \leq P_i \leq 10^9$.