Partially Free Meal
Description
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?
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.
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.
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.
3
2 5
4 3
3 7
7
11
16