← 返回题目列表

AtCoder · chokudai_S002_i

I. 胜山德君β

中文机器翻译题面 查看原题

配点 : 400 点

問題文

卡司三明治君喜欢蛋包饭。

另外我还喜欢明太子、寿司、奶油布丁和嫩腰肉牛排等。

现在,在炸猪排三明治君面前 N 喜爱的食物种类正摆在他面前。 炸猪排三明治君决定从中决定最强的食物。通过炸猪排三明治君的独特调查,食物

的 i 发现体力是 A_i、攻撃力是 B_i 。 在食物 i 与食物 j 战斗的情况下,胜败按照以下顺序决定。(也请参照输入输出示例。)

  1. 各食物互相攻击对方。食物 i 的体力减少 B_j ,食物 j 的体力减少 B_i 体力减少。
  2. 体力为 0 以下的食物会变成战斗不能状态。
  3. 如果任何食物都没有变成战斗不能状态,则返回步骤 1。
  4. 如果双方都变成战斗不能状态,则为平局;如果只有一方变成战斗不能状态,则另一方获胜。

卡司三明治君决定,将能够战胜其他任何食物的食物称为最强的食物。请找出最强的食物是哪个食物。

制約

输入满足以下条件。

  • 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 战斗的情况下如下。
    1. 开始,2 个食物的体力各自为 7, 9 。
    2. 互相进行攻击,各自的体力为 5, 6 变为。 给出了
    3. 互相进行攻击,各自的体力为 3, 3 变为。 给出了
    4. 互相进行攻击,各自的体力为 1, 0 变为。 给出了
    5. 食物 2 仅战斗不能,因此食物 1 获胜。
  • 食物 1 与食物 3 战斗的情况下如下。
    1. 开始,2 个食物的体力各自为 7, 2 。
    2. 互相进行攻击,各自的体力为 2, -1 变为。 给出了
    3. 食物 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