MianKing 这学期选修了一门课程。这门课共有 $n$ 名学生，每个人都需要写一篇期末论文。设 $w_i$ 表示第 $i$ 名学生论文的字数。

第 $i$ 名学生论文字数的下界为 $L_i$，上界为 $R_i$，即满足 $L_i \le w_i \le R_i$。

这门课的评分规则非常奇特。第 $i$ 名学生的成绩 $g_i$ 为 $n - K_i$，其中 $K_i$ 是满足 $w_j > w_i$ 的 $j \in [1, n]$ 的数量。

每名学生都希望获得尽可能高的成绩，因此在最优决策下，第 $i$ 名学生的 $w_i$ 将等于 $R_i$。

但 MianKing 发现了一个有趣的现象：假设对于所有 $i \in [1, n]$，都有 $L_i = 1000, R_i = 10000$。在最优决策下，所有 $w_i$ 都等于 $10000$，且所有学生的成绩都是 $n$。但如果每个人都只写 $1000$ 字的论文，他们的成绩依然都是 $n$，并且他们可以将节省下来的时间用来玩游戏。

为了对抗内卷，MianKing 想要为每名学生决定 $w_i$，他的计划必须满足以下条件： 1. 对于每名学生，其成绩不能低于原始计划（即 $w_i = R_i$ 时）的成绩。 2. 最小化 $\sum_{i=1}^n w_i$。

你需要帮助 MianKing 计算 $\sum_{i=1}^n w_i$ 的最小值。

输入格式

第一行包含一个整数 $n$。 接下来 $n$ 行，第 $i$ 行包含两个整数 $L_i, R_i$。

$1 \le n \le 10^5$ $1 \le L_i \le R_i \le 10^9$

输出格式

输出 $\sum_{i=1}^n w_i$ 的最小值。

样例

输入 1

3
1 10000
1 10000
1 10000

输出 1

3

输入 2

4
1 2
2 2
2 4
3 4

输出 2

10