说明

你有许多电脑，它们的硬盘用不同的文件系统储存数据。你想要通过格式化来统一文件系统。格式化硬盘可能使它的容量发生变化。为了格式化，你需要买额外的硬盘。当然，你想要买容量最小的额外储存设备以便省钱。你可以按任意顺序格式化硬盘。格式化之前，你要把该硬盘上所有数据移到一个或更多的其他硬盘上（可以分割数据）。格式化后，该硬盘可以立刻开始使用。你没有必要把数据放到它原来所在的硬盘上。数据也可以被放到你额外买的硬盘上。举个例子，假设你有 4 个硬盘 A、B、C、D，容量分别为 6、1、3、3(GB)。新的文件系统下，它们的容量变为 6、7、5、5(GB)。如果你只买 1GB 额外空间，你可以把B硬盘的数据放过去然后格式化硬盘 B。现在你的 B 硬盘有 7GB 容量了，那么你就可以把 A 的数据放过去然后格式化 A，最后把 C、D 的数据放到 A 上，再格式化 C 和 D。

输入格式

第一行一个数 $n(1≤n≤1,000,000)$，表示你的硬盘数。接下来 $n$ 行，每行两个数 $a$ 和 $b$，分别表示该硬盘的原容量和新文件系统下的容量。所有容量都以 GB 为单位，且$1≤a,b≤1,000,000,000$。

输出格式

输出如果要格式化所有硬盘，你最少需要购买多少额外空间(GB)。

4
6 6
1 7
3 5
3 5

1

4
2 2
3 3
5 1
5 10

5