题目描述

Smart 正在玩一个电脑游戏，现在他必须杀死 \(n\) 个怪兽。 这些怪兽围成一个圆圈，从 \(1\) 到 \(n\) 顺时针编号。 最初，第 \(i\) 个怪兽具有 \(a[i]\) 点生命值。

Smart 可以直接射击怪兽杀死它们，每发射击需要一颗子弹，并使被射击的怪兽的生命值减少 \(1\)（即对其造成 \(1\) 点伤害）。此外，当某个怪兽 \(i\) 的生命值变为 \(0\) 或小于 \(0\) 时，它会死亡并爆炸，对下一个(如果\(i \lt n\)，则下一个怪兽的编号为\(i+1\)；如果\(i=n\)，则下一个怪兽的编号为\(1\)）怪兽造成\(b[i]\)点伤害。如果下一个怪兽已经死了，那么就什么也不会发生，如果第 \(i\) 个怪兽爆炸杀死了下一个怪兽，那它也会爆炸，在它之后的怪兽也会受到伤害并可能引发另一次爆炸，依此类推。

请你帮助 Smart 计算杀死该圆圈子中所有 \(n\) 个怪兽所需发射的最少子弹数。

格式

输入格式

第一行一个整数 \(n\)，表示圆圈中怪兽的数量。

接下来 \(n\) 行，每行两个整数 \(a[i]\) 和 \(b[i]\)，含义如题中所述。

输出格式

输出一行包含一个整数，表示杀死该圆圈子中所有 \(n\) 个怪兽所需发射的最少子弹数。

样例1

输入样例1

3
7 15
2 14
5 3

输出样例1

6

样例解释

射死第 \(2\) 只怪兽需要 \(2\) 颗子弹，第 \(2\) 只怪兽死掉并爆炸导致第 \(3\) 只怪兽死掉并爆炸，第 \(3\) 只怪兽爆炸导致第 \(1\) 只怪兽受到 \(3\) 点伤害，还剩下 \(4\) 点生命值，再需要射击 \(4\) 颗子弹后才能死掉，所以共射击的最少子弹数为 \(2+4=6\)。

限制

\(100\%\)的数据：\(2\le n\le 300000，1\le a[i],b[i]\le 10^{12}\)。