B - Scholarship Selection Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は大学の奨学金選考委員会の担当者として、今年度の奨学金受給者を決定する作業を任されています。

今年の奨学金には N 人の学生が応募しており、それぞれの学生には 1 から N までの番号が付けられています。選考では M 科目の成績（点数）が評価対象となっており、学生 i の科目 j における成績は S_{i,j} 点です。

また、各科目 j にはそれぞれ最低基準点 T_j が設定されています。奨学金の受給者は以下の手順で決定されます。

ステップ 1：基準通過者の決定

学生 i が すべての 科目 j (1 \leq j \leq M) について S_{i,j} \geq T_j を満たすとき、その学生を「基準通過者」と呼びます。

ステップ 2：受給者の決定

基準通過者の人数に応じて、以下のように受給者を決定します。ここで K は選考の基準人数として与えられる正の整数です。

  • 基準通過者が K 人以下の場合、基準通過者全員を受給者とします。特に、基準通過者が 0 人の場合、受給者は 0 人です。
  • 基準通過者が K 人より多い場合、次のようにして受給者を選びます。各基準通過者 i について、全科目の成績の合計点 \displaystyle P_i = \sum_{j=1}^{M} S_{i,j} を求めます。基準通過者全員の P_i の値を降順にソートしたとき、大きい方から K 番目の値をボーダーライン B とします（基準通過者は K 人より多いので、K 番目の値は必ず存在します）。P_i \geq B であるような基準通過者全員を受給者とします。

> 注意： ボーダーライン B と同じ合計点を持つ基準通過者が複数いる場合、受給者の人数は K 人を超えることがあります。

高橋君の代わりに、受給者の学生番号を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10
  • 1 \leq K \leq N
  • 0 \leq T_j \leq 1000 (1 \leq j \leq M)
  • 0 \leq S_{i,j} \leq 1000 (1 \leq i \leq N, 1 \leq j \leq M)
  • 入力はすべて整数である。

入力

N M K
T_1 T_2 \ldots T_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、選考の基準人数を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、各科目の最低基準点を表す整数 T_1, T_2, \ldots, T_M が、スペース区切りで与えられる。
  • 3 行目から N + 2 行目までの N 行では、各学生の成績が与えられる。
  • 2 + i 行目には、学生 i の各科目の成績を表す整数 S_{i,1}, S_{i,2}, \ldots, S_{i,M} がスペース区切りで与えられる。

出力

受給者の学生番号を昇順に、1 行に 1 つずつ出力してください。受給者が 0 人の場合は何も出力しないでください（空出力）。

入力例 1

5 3 2
50 60 55
80 70 60
40 80 70
90 65 80
55 60 55
70 75 90

出力例 1

3
5

入力例 2

8 2 3
30 30
50 50
80 90
40 60
70 80
20 90
60 90
90 80
35 65

出力例 2

2
4
6
7

入力例 3

10 4 5
70 65 60 75
80 70 65 80
50 90 80 70
75 68 62 90
60 65 70 80
90 80 75 85
72 66 61 76
30 40 50 60
85 70 60 80
70 65 60 74
95 85 80 90

出力例 3

1
3
5
8
10

Score : 300 pts

Problem Statement

Takahashi has been assigned the task of determining this year's scholarship recipients as a member of the university's scholarship selection committee.

This year, N students have applied for the scholarship, and each student is assigned a number from 1 to N. The selection evaluates grades (scores) in M subjects, where student i's score in subject j is S_{i,j} points.

Additionally, each subject j has a minimum threshold score T_j. The scholarship recipients are determined by the following procedure.

Step 1: Determining Qualifying Students

Student i is called a "qualifying student" if they satisfy S_{i,j} \geq T_j for all subjects j (1 \leq j \leq M).

Step 2: Determining Recipients

Recipients are determined based on the number of qualifying students as follows. Here, K is a positive integer given as the selection quota.

  • If the number of qualifying students is K or fewer, all qualifying students become recipients. In particular, if there are 0 qualifying students, then there are 0 recipients.
  • If the number of qualifying students is more than K, recipients are selected as follows. For each qualifying student i, compute the total score across all subjects \displaystyle P_i = \sum_{j=1}^{M} S_{i,j}. Sort the P_i values of all qualifying students in descending order, and let the K-th value from the top be the borderline B (since there are more than K qualifying students, the K-th value always exists). All qualifying students with P_i \geq B become recipients.

> Note: If multiple qualifying students have the same total score as the borderline B, the number of recipients may exceed K.

On behalf of Takahashi, determine the student numbers of the recipients.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10
  • 1 \leq K \leq N
  • 0 \leq T_j \leq 1000 (1 \leq j \leq M)
  • 0 \leq S_{i,j} \leq 1000 (1 \leq i \leq N, 1 \leq j \leq M)
  • All input values are integers.

Input

N M K
T_1 T_2 \ldots T_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 three space-separated integers: N representing the number of applicant students, M representing the number of subjects, and K representing the selection quota.
  • The second line contains space-separated integers T_1, T_2, \ldots, T_M representing the minimum threshold scores for each subject.
  • The following N lines (from line 3 to line N + 2) give each student's scores.
  • The (2 + i)-th line contains space-separated integers S_{i,1}, S_{i,2}, \ldots, S_{i,M} representing student i's scores in each subject.

Output

Output the student numbers of the recipients in ascending order, one per line. If there are 0 recipients, output nothing (empty output).

Sample Input 1

5 3 2
50 60 55
80 70 60
40 80 70
90 65 80
55 60 55
70 75 90

Sample Output 1

3
5

Sample Input 2

8 2 3
30 30
50 50
80 90
40 60
70 80
20 90
60 90
90 80
35 65

Sample Output 2

2
4
6
7

Sample Input 3

10 4 5
70 65 60 75
80 70 65 80
50 90 80 70
75 68 62 90
60 65 70 80
90 80 75 85
72 66 61 76
30 40 50 60
85 70 60 80
70 65 60 74
95 85 80 90

Sample Output 3

1
3
5
8
10