Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

L. Partially Free Meal
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

A new restaurant is opened in Byteland. To attract more customers, the meal is partially free. Specifically, there are $$$n$$$ types of dishes on sale, labeled by $$$1,2,\dots,n$$$. Each dish can not be ordered more than once. For the $$$i$$$-th dish, its basic price is $$$a_i$$$ dollars, and its event price is $$$b_i$$$ dollars. Assume you have ordered $$$k$$$ dishes $$$p_1,p_2,\dots,p_k$$$ ($$$1\leq p_i\leq n, p_i<p_{i+1}$$$), the total amount of dollars that you need to pay for is:

$$$$$$ \sum_{i=1}^k a_{p_i}+\max_{i=1}^k\left\{b_{p_i}\right\} $$$$$$

You are a customer at this restaurant, you decide to order exactly $$$k$$$ dishes, what's the minimum possible amount of dollars that you need to pay for?

Input

The first line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 200\,000$$$), denoting the number of dishes.

Each of the following $$$n$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i,b_i \leq 10^9$$$), denoting the basic price and the event price of each dish.

Output

Print $$$n$$$ lines, the $$$k$$$-th ($$$1\leq k\leq n$$$) of which containing an integer, denoting the minimum possible amount of dollars that you need to pay for when you order exactly $$$k$$$ dishes.

Example
Input
3
2 5
4 3
3 7
Output
7
11
16