AT_chokudai_S002_i カツサンドくん β

[problemUrl]: https://atcoder.jp/contests/chokudai_S002/tasks/chokudai_S002_i > [カツサンドくんはオムライスが好きです。](https://atcoder.jp/contests/abc118/tasks/abc118_b) > > 他にも明太子や寿司、クリームブリュレやテンダーロインステーキなどが好きです。 今、カツサンドくんの目の前には $ N $ 種類の好きな食べ物が並んでいます。 カツサンドくんはこの中から**最強の食べ物**を決めることにしました。 カツサンドくんの独自の調査により、食べ物 $ i $ の**体力**が $ A_i $、**攻撃力**が $ B_i $ であることが分かりました。 食べ物 $ i $ と食べ物 $ j $ が戦った場合、以下の手順で勝敗が決まります。（入出力例も参考にしてください。） 1. 各食べ物が互いを攻撃し合う。食べ物 $ i $ の体力が $ B_j $ だけ減少し、食べ物 $ j $ の体力が $ B_i $ だけ減少する。 2. 体力が $ 0 $ 以下になった食べ物は戦闘不能になる。 3. いずれの食べ物も戦闘不能になっていない場合は手順 1. に戻る。 4. 両方が戦闘不能になった場合は引き分け、片方のみが戦闘不能になった場合はもう片方の勝利とする。 カツサンドくんは、他のどの食べ物と戦ったとしても勝利できるような食べ物を最強の食べ物とすることにしました。最強の食べ物がどの食べ物であるかを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ : $ $ A_N $ $ B_N $

最強の食べ物の番号を出力せよ。ただし、最強の食べ物が存在しない場合は代わりに `-1` を出力せよ。

### 制約 入力は以下の条件を満たす。 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ A_i,B_i\ \leq\ 10^9 $ - 入力される値は全て整数 ### Sample Explanation 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 $ の勝利となる。 ### Sample Explanation 2 食べ物 $ 1 $ と食べ物 $ 2 $ が戦った場合、最初の攻撃の後両方の食べ物が戦闘不能になり、引き分けとなります。 このため、最強の食べ物は存在しません。