分数: 300 分
问题陈述
高桥作为学校奖学金评选委员会的成员,被指派负责确定今年的奖学金获得者。
今年, N 学生已申请奖学金,每个学生都被分配了一个编号 1 to N。选择评估等级(分数) M 科目,学生所在位置 i的科目成绩 j is S_{i,j} 点。
此外,每个科目 j 有最低阈值分数 T_j。奖学金获得者按照以下程序确定。
第 1 步:确定合格学生
学生 i 如果满足以下条件,则被称为“合格学生” S_{i,j} \geq T_j 为 全部 科目 j (1 \leq j \leq M).
第 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.
代表 Takahashi 确定收件人的学生编号。
约束
- 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}
- 第一行包含三个空格分隔的整数: N 代表申请学生人数, M 代表受试者数量,以及 K 代表选拔名额。
- 第二行包含空格分隔的整数 T_1, T_2, \ldots, T_M 代表每个科目的最低阈值分数。
- 以下 N 行(来自行 3 转线 N + 2) 给出每个学生的分数。
- 的 (2 + i)- 第行包含空格分隔的整数 S_{i,1}, S_{i,2}, \ldots, S_{i,M} 代表学生 i每个科目的分数。
输出
按升序输出收件人的学号,每行一个。如果有 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