Hungry Mirko’s Restaurant

Mirko is as hungry as a bear and has found a local restaurant offering N different dishes. Each dish has two specified prices \(A_i\) and \(B_i\). When Mirko orders some dishes, only the first dish is charged at its \(A\) price, and all the remaining dishes are charged at their respective \(B\) prices. Mirko does not care about the order or which dishes he selects (each dish can be chosen at most once), and he just wants to know the minimum cost for every possible number \(k\) (with \(1 \le k \le N\)) of dishes he might order.

More formally, given \(N\) dishes where the i-th dish has two prices \(A_i\) and \(B_i\), if Mirko orders exactly \(k\) dishes and chooses one of them as the first dish (to pay \(A_i\)) and the remaining \(k-1\) dishes at their \(B\) prices, determine the minimum total cost among all possible choices of \(k\) distinct dishes. For \(k=1\), the cost is simply \(A_i\) for some dish \(i\).

The answer for each \(k\) should be computed as follows:

[ \min_{1 \le i \le N} \Bigl{ A_i + \Bigl(\text{if dish } i \text{ is among the smallest } (k-1) \text{ in } B \text{ then } \bigl(\sum_{\ell=1}^{k} B_{\ell} - B_i\bigr) \text{ else } \sum_{\ell=1}^{k-1} B_{\ell} \Bigr) \Bigr} ]

Note that our selection for the remaining \(k-1\) dishes always uses the dishes with the smallest \(B\) values excluding the dish used for the \(A\) price.

inputFormat

The first line contains a single integer \(N\) representing the number of dishes. Each of the next \(N\) lines contains two integers \(A_i\) and \(B_i\) separated by a space, which denote the two prices for the \(i\)-th dish.

\(1 \le N \le 10^5\); \(1 \le A_i, B_i \le 10^9\).

outputFormat

Output \(N\) lines. The \(k\)-th line (for \(1 \le k \le N\)) should contain the minimum total cost to order exactly \(k\) distinct dishes.

sample

3
3 1
2 2
3 1

2
3
4