Problem Description

Mirko is as hungry as a bear and has discovered a local restaurant. This restaurant offers $N$ meals, each with an interesting pricing policy: every meal has two designated prices, $A_i$ and $B_i$. For the first meal Mirko orders, he only needs to pay $A$ dollars, while for any subsequent meals, he needs to pay $B$ dollars.

Mirko can't decide how many meals to order. To make it simpler to decide, he seeks your help. For any $k \in [1, N]$, you need to determine the minimum amount of money Mirko needs to pay to order $k$ different meals. Mirko doesn't care which specific meals he orders or the order in which he orders them, but he will not order the same meal twice.

Input Format

The first line contains a positive integer $N$ $(2 \le N \le 5 \times 10^5)$, representing the number of meals.

The next $N$ lines each contain two positive integers $A_i, B_i$ $(1 \le A_i, B_i \le 10^9)$, as described in the problem.

Output Format

The output should consist of $N$ lines. The $k$-th line should indicate the minimum amount of money needed to order $k$ different meals.

Sample Input and Output

Sample Input #1

3
10 5
9 3
10 5

Sample Output #1

9
13
18

Sample Input #2

2
100 1
1 100

Sample Output #2

1
2

Sample Input #3

5
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

Sample Output #3

1000000000
2000000000
3000000000
4000000000
5000000000

Notes

Explanation for Sample #1

• For $k=1$: Mirko starts by ordering the second meal, spending $A_2 = 9$ dollars.
• For $k=2$: Mirko starts by ordering the first meal, then the second meal, spending $A_1 + B_2 = 13$ dollars.
• For $k=3$: Mirko starts by ordering the first meal, then the second and third meals, spending $A_1 + B_2 + B_3 = 18$ dollars.

见题面 Input 部分

见题面 Output 部分