You have recently been learning how to play games.

There are $n$ monsters. Defeating the $i$-th monster costs $A_i$ stamina, and after defeating it, you gain $B_i$ stamina. At any moment, your stamina cannot be negative.

For each $k = 1, 2, \cdots, n$, find the minimum initial stamina required to defeat $k$ monsters.

Input

The first line contains two positive integers $n$ and $m$.

The next $n$ lines each contain two integers $A_i$ and $B_i$, representing the attributes of the monsters.

Output

Output a single line containing $n$ non-negative integers, where the $i$-th integer represents the minimum initial stamina required to defeat $i$ monsters.

Examples

Input 1

4
1 2
3 4
1 1
2 3

Output 1

1 2 3 4

Input 2

8
304 282
773 724
274 481
43 254
813 110
722 107
140 62
351 418

Output 2

43 43 63 63 63 288 341 1044

Constraints

• Subtask 1 (5 points): $n \leq 16$.
• Subtask 2 (27 points): $n \leq 7000$.
• Subtask 3 (68 points): No additional constraints.

For 100% of the data, $1 \leq n \leq 3 \times 10^5$ and $1 \leq A_i, B_i \leq 10^9$.