题目描述

有一个岛，岛上有 $n$ 个位置，这些位置用环形的道路连接而成。其中第 $i$ 个位置到下一个位置需要消耗 $c_i$ 个单位的汽油，而在第 $i$ 个位置可以补给 $p_i$ 个单位的汽油。对于第 $n$ 位置来说，下一个位置就是第 $1$ 个位置。道路都是单向的。

你在出发时车上没有任何汽油，你可以选择任意一个位置出发，车辆的油箱无限大。请问从哪一个位置出发，可以回到起点，且这个位置的编号最小？

输入格式

• 第一行：单个整数表示 $n$
• 第二行到第 $n+1$ 行：每行两个数表示 $p_i$ 与 $c_i$

输出格式

• 单个整数：表示答案，如果没有任何可行位置，输出 0

5
3 5
2 1
5 6
3 5
9 4

5

样例解释 1

从5号点出发

数据范围

• $30\%$ 的数据，$2\leq n\leq 1,000$
• $60\%$ 的数据，$2\leq n\leq 30,000$
• $100\%$ 的数据，$2\leq n\leq 500,000$
• $1\leq c_i,p_i\leq 1,000,000,000$