你管理着一个大型计算机集群，其中的硬盘使用各种文件系统来存储数据。你最近决定将所有硬盘的文件系统统一为同一种类型。这极具挑战性，因为所有硬盘目前都在使用中，且都已存满了重要数据，达到其容量极限，你无法承受任何数据丢失。此外，将硬盘重新格式化为新文件系统可能会显著改变其容量。为了使重新格式化成为可能，你必须购买一块额外的硬盘。显然，你希望通过最小化这种额外存储空间的大小来节省开支。

你可以按任意顺序重新格式化硬盘。在重新格式化某块硬盘之前，你必须将该硬盘上的所有数据移动到一块或多块其他硬盘上，必要时可以拆分数据。硬盘重新格式化后，你可以立即开始使用它来存储来自其他硬盘的数据。不必将所有数据放回它们最初所在的硬盘上——事实上，如果某些硬盘在新文件系统下的容量较小，这甚至可能是不可能的。也允许将部分数据存放在额外的硬盘上。

例如，假设你有四块硬盘 $A, B, C$ 和 $D$，容量分别为 $6, 1, 3$ 和 $3$ GB。在新文件系统下，它们的容量分别变为 $6, 7, 5$ 和 $5$ GB。如果你只购买 $1$ GB 的额外空间，你可以将硬盘 $B$ 上的数据移动到那里，然后重新格式化硬盘 $B$。现在硬盘 $B$ 上有 $7$ GB 的空闲空间，因此你可以将硬盘 $A$ 上的 $6$ GB 数据移动到那里，并重新格式化硬盘 $A$。最后，你将硬盘 $C$ 和 $D$ 上的总共 $6$ GB 数据移动到硬盘 $A$ 上，并重新格式化 $C$ 和 $D$。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示集群中硬盘的数量。接下来有 $n$ 行，每行描述一块硬盘，包含两个整数 $a$ 和 $b$，其中 $a$ 是旧文件系统下的容量，$b$ 是新文件系统下的容量。

所有容量均以 GB 为单位，且满足 $1 \le a, b \le 10^9$。

输出格式

输出你为了重新格式化所有硬盘所必须购买的额外总容量（以 GB 为单位）。

样例

样例输入 1

4
6 6
1 7
3 5
3 5

样例输出 1

1

样例输入 2

4
2 2
3 3
5 1
5 10

样例输出 2

5