P8298 [COCI 2012/2013 #2] POPUST

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

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.

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 $N$ lines. The $k$-th line should be the minimum amount of money needed to order $k$ distinct dishes.

#### 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