A - Cooking Contest Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君の町で料理コンテストが開催されます。このコンテストでは、各参加者が料理を作り、その総合得点を競います。

コンテストには N 人の参加者がいます。i 番目の参加者の料理の「味の得点」は H_i 点、「盛り付けの得点」は S_i 点です。さらに、各参加者は特別な食材を使用しており、その食材による「ボーナス得点」が D_i 点加算されます。

つまり、i 番目の参加者の総合得点は H_i + S_i + D_i 点となります。

審査員の青木君は、特別な食材の影響を除いた純粋な料理の腕前を評価したいと考えています。具体的には、各参加者の総合得点からボーナス得点 D_i を差し引いた値 H_i + S_i を「実力値」と定義しました。

青木君は、すべての参加者の中で実力値が最大である参加者を優勝者としたいです。実力値が最大の参加者の番号を求めてください。なお、実力値が最大の参加者はちょうど一人であることが保証されます。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq H_i \leq 10^9
  • 0 \leq S_i \leq 10^9
  • 0 \leq D_i \leq 10^9
  • 実力値 H_i + S_i が最大の参加者はちょうど一人である。
  • 入力はすべて整数である。

入力

N
H_1 S_1 D_1
H_2 S_2 D_2
:
H_N S_N D_N
  • 1 行目には、参加者の人数を表す N が与えられる。
  • 2 行目から N + 1 行目では、各参加者の情報が N 行で与えられる。
  • 1 + i 行目では、i 番目の参加者の味の得点 H_i 、盛り付けの得点 S_i 、ボーナス得点 D_i が、スペース区切りで与えられる。

出力

実力値 H_i + S_i が最大である参加者の番号を 1 行で出力せよ。

入力例 1

3
5 3 10
7 6 1
3 8 20

出力例 1

2

入力例 2

4
1 1 1000000000
100 200 0
50 50 999999999
150 149 500000000

出力例 2

2

入力例 3

10
80 90 50
70 60 200
100 100 10
55 45 300
90 85 15
60 70 400
95 80 25
40 30 500
85 95 5
75 65 100

出力例 3

3

入力例 4

20
500000000 500000000 0
499999999 500000000 1000000000
400000000 300000000 999999999
100000000 200000000 800000000
350000000 350000000 500000000
450000000 450000000 100000000
999999999 0 999999999
0 999999998 999999999
123456789 876543200 0
500000000 499999999 300000000
600000000 300000000 200000000
200000000 700000000 400000000
800000000 100000000 500000000
150000000 750000000 600000000
300000000 600000000 100000000
700000000 200000000 50000000
250000000 650000000 350000000
450000000 400000000 250000000
550000000 350000000 150000000
100000000 100000000 999999999

出力例 4

1

入力例 5

1
0 0 1000000000

出力例 5

1

Score : 233 pts

Problem Statement

A cooking contest is being held in Takahashi's town. In this contest, each participant prepares a dish and competes based on their total score.

There are N participants in the contest. The i-th participant's dish has a "taste score" of H_i points and a "presentation score" of S_i points. Additionally, each participant uses a special ingredient, which grants them a "bonus score" of D_i points.

In other words, the i-th participant's total score is H_i + S_i + D_i points.

Judge Aoki wants to evaluate the pure cooking skill of each participant, excluding the influence of the special ingredient. Specifically, he defined the "skill value" as the value obtained by subtracting the bonus score D_i from each participant's total score, which is H_i + S_i.

Aoki wants the participant with the highest skill value among all participants to be the winner. Find the number of the participant with the highest skill value. It is guaranteed that there is exactly one participant with the highest skill value.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq H_i \leq 10^9
  • 0 \leq S_i \leq 10^9
  • 0 \leq D_i \leq 10^9
  • There is exactly one participant whose skill value H_i + S_i is the maximum.
  • All input values are integers.

Input

N
H_1 S_1 D_1
H_2 S_2 D_2
:
H_N S_N D_N
  • The first line contains N, the number of participants.
  • From the 2nd line to the (N + 1)-th line, information about each participant is given over N lines.
  • The (1 + i)-th line contains the taste score H_i, the presentation score S_i, and the bonus score D_i of the i-th participant, separated by spaces.

Output

Print the number of the participant whose skill value H_i + S_i is the maximum, in a single line.

Sample Input 1

3
5 3 10
7 6 1
3 8 20

Sample Output 1

2

Sample Input 2

4
1 1 1000000000
100 200 0
50 50 999999999
150 149 500000000

Sample Output 2

2

Sample Input 3

10
80 90 50
70 60 200
100 100 10
55 45 300
90 85 15
60 70 400
95 80 25
40 30 500
85 95 5
75 65 100

Sample Output 3

3

Sample Input 4

20
500000000 500000000 0
499999999 500000000 1000000000
400000000 300000000 999999999
100000000 200000000 800000000
350000000 350000000 500000000
450000000 450000000 100000000
999999999 0 999999999
0 999999998 999999999
123456789 876543200 0
500000000 499999999 300000000
600000000 300000000 200000000
200000000 700000000 400000000
800000000 100000000 500000000
150000000 750000000 600000000
300000000 600000000 100000000
700000000 200000000 50000000
250000000 650000000 350000000
450000000 400000000 250000000
550000000 350000000 150000000
100000000 100000000 999999999

Sample Output 4

1

Sample Input 5

1
0 0 1000000000

Sample Output 5

1