A - Figure Skating Scoring Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は、フィギュアスケートの大会で採点結果の集計を担当することになりました。

この大会には N 人の選手が出場しており、選手には 1 から N までの番号がついています。それぞれの選手は M 人の審査員から評価を受けます。選手 i (1 \leq i \leq N) が審査員 j (1 \leq j \leq M) から受けた点数を S_{i,j} とします。各点数は 1 以上 100 以下の整数です。

大会の規定により、各選手の最終スコアは以下の手順で計算されます：

  1. M 人の審査員がつけた M 個の点数を、値の小さい順（昇順）に並べる。
  2. 並べた点数の先頭（最小値）の 1 個と末尾（最大値）の 1 個を除外する。同じ値の点数が複数あっても、除外するのはそれぞれ 1 個のみである。
  3. 残った M - 2 個の点数の合計を、その選手の最終スコアとする。

最終スコアが最も高い選手の番号を出力してください。最終スコアが最も高い選手が複数いる場合は、その中で番号が最も小さい選手の番号を出力してください。

制約

  • 1 \leq N \leq 10^5
  • 3 \leq M \leq 10^5
  • N \times M \leq 10^6
  • 1 \leq S_{i,j} \leq 100
  • 入力はすべて整数である。

入力

N M
S_{1,1} S_{1,2} \ldots S_{1,M}
S_{2,1} S_{2,2} \ldots S_{2,M}
\vdots
S_{N,1} S_{N,2} \ldots S_{N,M}
  • 1 行目には、選手の人数を表す N と審査員の人数を表す M が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各選手が受けた点数が与えられる。
  • 1 + i 行目では、選手 i が M 人の審査員から受けた点数 S_{i,1}, S_{i,2}, \ldots, S_{i,M} がスペース区切りで与えられる。

出力

最終スコアが最も高い選手の番号を 1 行で出力してください。

入力例 1

3 3
5 9 3
8 6 7
4 10 1

出力例 1

2

入力例 2

5 5
50 60 70 80 90
65 75 70 85 55
90 40 80 70 60
100 100 1 1 50
72 68 75 80 71

出力例 2

5

入力例 3

4 7
80 75 90 60 85 70 95
88 92 78 85 90 83 79
95 91 89 84 87 93 86
100 70 99 88 92 91 85

出力例 3

4

Score : 266 pts

Problem Statement

Takahashi has been assigned to tally the scoring results at a figure skating competition.

There are N contestants in this competition, numbered from 1 to N. Each contestant is evaluated by M judges. Let S_{i,j} denote the score that contestant i (1 \leq i \leq N) received from judge j (1 \leq j \leq M). Each score is an integer between 1 and 100, inclusive.

According to the competition rules, each contestant's final score is calculated by the following procedure:

  1. Sort the M scores given by the M judges in ascending order (from smallest to largest).
  2. Remove the first score (the minimum) and the last score (the maximum) from the sorted list. Even if there are multiple scores with the same value, only one score is removed from each end.
  3. The sum of the remaining M - 2 scores becomes that contestant's final score.

Output the number of the contestant with the highest final score. If there are multiple contestants with the highest final score, output the smallest number among them.

Constraints

  • 1 \leq N \leq 10^5
  • 3 \leq M \leq 10^5
  • N \times M \leq 10^6
  • 1 \leq S_{i,j} \leq 100
  • All input values are integers.

Input

N M
S_{1,1} S_{1,2} \ldots S_{1,M}
S_{2,1} S_{2,2} \ldots S_{2,M}
\vdots
S_{N,1} S_{N,2} \ldots S_{N,M}
  • The first line contains N, the number of contestants, and M, the number of judges, separated by a space.
  • From the 2nd line to the (N + 1)-th line, the scores received by each contestant are given.
  • The (1 + i)-th line contains the scores S_{i,1}, S_{i,2}, \ldots, S_{i,M} that contestant i received from the M judges, separated by spaces.

Output

Output the number of the contestant with the highest final score on a single line.

Sample Input 1

3 3
5 9 3
8 6 7
4 10 1

Sample Output 1

2

Sample Input 2

5 5
50 60 70 80 90
65 75 70 85 55
90 40 80 70 60
100 100 1 1 50
72 68 75 80 71

Sample Output 2

5

Sample Input 3

4 7
80 75 90 60 85 70 95
88 92 78 85 90 83 79
95 91 89 84 87 93 86
100 70 99 88 92 91 85

Sample Output 3

4