Background

The score for this problem follows the original COCI settings, with a full score of $120$.

Problem Description

Mirko is as hungry as a bear and finds a local restaurant. This restaurant offers $N$ meals and has an interesting pricing policy: each meal has two specified prices, $A_i$ and $B_i$. The first dish Mirko orders only costs $A$ money, and all other dishes cost $B$ money.

Mirko cannot decide how many dishes to order. To make the decision easier, he asks you for help. For any $k\in[1,N]$, find the minimum amount of money he needs to pay to order $k$ dishes. Mirko does not care which specific meals he orders, nor the order in which he orders them, but he will not order two identical dishes.

Input Format

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

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 statement.

Output Format

Output $N$ lines. The $k$-th line should be the minimum amount of money needed to order $k$ distinct dishes.

3
10 5
9 3
10 5

9
13
18

2
100 1
1 100

1
2

5
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

1000000000
2000000000
3000000000
4000000000
5000000000

Hint

Explanation for Sample #1

• $k=1$: Mirko starts by ordering the $2$-nd dish, with a total cost of $A_2=9$.

• $k=2$: Mirko starts by ordering the $1$-st dish, then orders the $2$-nd dish, with a total cost of $A_1+B_2=13$.

• $k=3$: Mirko starts by ordering the $1$-st dish, then orders dishes $2,3$, with a total cost of $A_1+B_2+B_3=18$.

Translated by ChatGPT 5