Byteland 开了一家新餐馆。为了吸引更多顾客，餐馆推出了部分免费的用餐活动。具体来说，店里有 $n$ 种菜品，编号为 $1, 2, \dots, n$。每种菜品最多只能点一次。对于第 $i$ 种菜品，其基础价格为 $a_i$ 美元，活动价格为 $b_i$ 美元。假设你点了 $k$ 道菜 $p_1, p_2, \dots, p_k$（其中 $1 \le p_i \le n$ 且 $p_i < p_{i+1}$），你需要支付的总金额为：

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

你是这家餐馆的一名顾客，你决定点恰好 $k$ 道菜，请问你需要支付的最小金额是多少？

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 200\,000$)，表示菜品的数量。 接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le 10^9$)，分别表示每种菜品的基础价格和活动价格。

输出格式

输出 $n$ 行，第 $k$ 行（$1 \le k \le n$）包含一个整数，表示点恰好 $k$ 道菜时需要支付的最小金额。

样例

样例输入 1

3
2 5
4 3
3 7

样例输出 1

7
11
16