I - カツサンドくん β
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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