Byteasar 倾向于推迟他需要完成的所有任务。然而，如果他承诺做某事，你绝对可以信赖他。

Byteasar 今天早早醒来，列出了一份他近期需要完成的任务清单。第 $i$ 个任务需要他花费 $d_i$ 个连续的天数来完成，并且必须在从今天算起的未来 $t_i$ 天内完成。Byteasar 想知道他最多可以有多少时间什么都不做，直到他真的必须开始执行某些任务。你能写一个程序来帮他找出这个时间吗？Byteasar 自己也可以写这样一个程序，但这可能会打扰他的拖延期。

输入格式

输入的第一行包含一个整数 $n$ ($1 \leqslant n \leqslant 1\,000\,000$)：Byteasar 需要完成的任务数量。接下来的 $n$ 行包含任务的描述。其中第 $i$ 行包含两个整数 $d_i$ 和 $t_i$ ($1 \leqslant d_i, t_i \leqslant 10^9$)。我们假设 Byteasar 能够按时完成所有任务。

输出格式

你的程序应该输出一个整数 $k$：Byteasar 可以避免工作的最大天数。换句话说，最迟在第 $k+1$ 天，Byteasar 必须开始执行其中一项任务，以便能够最终按时完成所有任务。

样例

输入 1

3
2 8
1 13
3 10

输出 1

5

说明

Byteasar 前 5 天休息。在接下来的 5 天里，他执行了第一个和第三个任务（按此顺序）。之后他休息了 1 天，然后执行了第二个任务，该任务花费了他 2 天时间。