#P18405. Partially Free Meal

Partially Free Meal

Partially Free Meal

Byteland 新开了一家餐馆。为了吸引顾客,餐馆推出了“部分免费”的活动。

餐馆出售 nn 种菜,编号为 1,2,…,n1,2,\ldots,n,每种菜至多点一次。第 ii 种菜的基础价格为 aia_i 美元,活动价格为 bib_i 美元。

假设你点了恰好 kk 种菜,编号依次为 p1,p2,…,pkp_1,p_2,\ldots,p_k,其中 1≤pi≤n1\le p_i\le n,且 pi<pi+1p_i<p_{i+1},则实际需要支付的总金额为

$$\sum_{i=1}^{k}a_{p_i}+\max_{1\le i\le k}\{b_{p_i}\}.$$

你是这家餐馆的顾客。对于每一个 k=1,2,…,nk=1,2,\ldots,n,请分别求出点恰好 kk 种菜时,可能支付的最少金额。

输入格式

第一行包含一个整数 nn(1≤n≤200 0001\le n\le200\,000),表示菜的种类数。

接下来 nn 行,每行包含两个整数 ai,bia_i,b_i(1≤ai,bi≤1091\le a_i,b_i\le10^9),分别表示第 ii 种菜的基础价格和活动价格。

输入只有一组数据。

输出格式

输出 nn 行。第 kk 行(1≤k≤n1\le k\le n)输出一个整数,表示点恰好 kk 种菜时的最少支付金额。

样例

3
2 5
4 3
3 7
7
11
16