B - Best Cost-Performance Laptop Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は大学に入学するにあたり、新しいノートPCを購入しようとしています。

高橋君は N 個のノートPCの候補を見つけました。i 番目 (1 \leq i \leq N) のノートPCには、価格 P_i 円と性能スコア S_i が決まっています。性能スコアは値が大きいほど性能が高いことを表します。

高橋君の先輩である青木君は、以前ノートPCを購入した際に性能を気にせず安さだけで選んでしまい、性能が低くて後悔した経験があります。そんな青木君から、「価格に対して性能が高いノートPCを選ぶべきだ」とアドバイスを受けました。

そこで高橋君は、i 番目のノートPCの「コストパフォーマンス」を \frac{S_i}{P_i} と定義し、N 個のノートPCの中からコストパフォーマンスが最大となるものを 1 つ選ぶことにしました。

コストパフォーマンスが最大となるノートPCの番号を求めてください。コストパフォーマンスが最大となるノートPCが複数ある場合は、その中で最も番号が小さいものを出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq P_i \leq 10^6
  • 1 \leq S_i \leq 10^6
  • 入力はすべて整数

入力

N
P_1 S_1
P_2 S_2
\vdots
P_N S_N

1 行目には、ノートPCの候補の数 N が与えられます。続く N 行のうち i 行目 (1 \leq i \leq N) には、i 番目のノートPCの価格 P_i と性能スコア S_i がスペース区切りで与えられます。

出力

コストパフォーマンスが最大となるノートPCの番号（1 から N までの整数）を 1 行で出力してください。コストパフォーマンスが最大となるノートPCが複数ある場合は、その中で最も番号が小さいものを出力してください。

入力例 1

3
80000 400
100000 600
120000 480

出力例 1

2

入力例 2

5
50000 250
60000 360
80000 480
90000 450
70000 420

出力例 2

2

入力例 3

8
150000 600
200000 1000
180000 720
120000 600
250000 1000
100000 500
80000 320
160000 800

出力例 3

2

Score : 300 pts

Problem Statement

Takahashi is about to enter university and is looking to purchase a new laptop.

Takahashi has found N candidate laptops. The i-th (1 \leq i \leq N) laptop has a price of P_i yen and a performance score of S_i. A higher performance score indicates better performance.

Takahashi's senior, Aoki, once bought a laptop choosing solely based on low price without considering performance, and regretted it because the performance was poor. Aoki advised Takahashi: "You should choose a laptop that has high performance relative to its price."

Following this advice, Takahashi defines the "cost performance" of the i-th laptop as \frac{S_i}{P_i}, and decides to choose the one with the maximum cost performance among the N laptops.

Find the number of the laptop with the maximum cost performance. If there are multiple laptops with the maximum cost performance, output the one with the smallest number.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq P_i \leq 10^6
  • 1 \leq S_i \leq 10^6
  • All inputs are integers

Input

N
P_1 S_1
P_2 S_2
\vdots
P_N S_N

The first line gives the number of candidate laptops N. In the following N lines, the i-th line (1 \leq i \leq N) gives the price P_i and performance score S_i of the i-th laptop, separated by a space.

Output

Output the number (an integer from 1 to N) of the laptop with the maximum cost performance in a single line. If there are multiple laptops with the maximum cost performance, output the one with the smallest number.

Sample Input 1

3
80000 400
100000 600
120000 480

Sample Output 1

2

Sample Input 2

5
50000 250
60000 360
80000 480
90000 450
70000 420

Sample Output 2

2

Sample Input 3

8
150000 600
200000 1000
180000 720
120000 600
250000 1000
100000 500
80000 320
160000 800

Sample Output 3

2