配点 : 400 点
問題文
另外我还喜欢明太子、寿司、奶油布丁和嫩腰肉牛排等。
现在,在炸猪排三明治君面前 N 喜爱的食物种类正摆在他面前。 炸猪排三明治君决定从中决定最强的食物。通过炸猪排三明治君的独特调查,食物
的 i 发现体力是 A_i、攻撃力是 B_i 。 在食物 i 与食物 j 战斗的情况下,胜败按照以下顺序决定。(也请参照输入输出示例。)
- 各食物互相攻击对方。食物 i 的体力减少 B_j ,食物 j 的体力减少 B_i 体力减少。
- 体力为 0 以下的食物会变成战斗不能状态。
- 如果任何食物都没有变成战斗不能状态,则返回步骤 1。
- 如果双方都变成战斗不能状态,则为平局;如果只有一方变成战斗不能状态,则另一方获胜。
卡司三明治君决定,将能够战胜其他任何食物的食物称为最强的食物。请找出最强的食物是哪个食物。
制約
输入满足以下条件。
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i,B_i \leq 10^9
- 输入的值全为整数。
入力
输入以以下格式从标准输入提供。
N A_1 B_1 A_2 B_2 : A_N B_N
出力
输出最强食物的编号。但是,如果不存在最强食物,则输出 -1 。
入力例 1
3 7 3 9 2 2 5
出力例 1
1
食物 1 能够战胜其他任何食物,因此是最强的食物。
- 食物 1 与食物 2 战斗的情况下如下。
- 开始,2 个食物的体力各自为 7, 9 。
- 互相进行攻击,各自的体力为 5, 6 变为。 给出了
- 互相进行攻击,各自的体力为 3, 3 变为。 给出了
- 互相进行攻击,各自的体力为 1, 0 变为。 给出了
- 食物 2 仅战斗不能,因此食物 1 获胜。
- 食物 1 与食物 3 战斗的情况下如下。
- 开始,2 个食物的体力各自为 7, 2 。
- 互相进行攻击,各自的体力为 2, -1 变为。 给出了
- 食物 3 仅战斗不能,因此食物 1 获胜。
入力例 2
2 999999999 1000000000 1 999999999
出力例 2
-1
食物 1 与食物 2 战斗的情况下,第一次攻击后双方食物都战斗不能,判定为平局。 因此,最强的食物不存在。
入力例 3
2 999999999 1 1000000000 1
出力例 3
2
入力例 4
3 100 17 171 10 91 19
出力例 4
-1