P16461 [UOI 2026] Lazy Student

Kozak Vus 是一名大学生。在第一学期，他面临 $n$ 门科目和 $m$ 周的学习。Vus 提前知道了所有的作业，为了方便，他估算了它们的难度。他制作了一张 $n \times m$ 的表格，其中第 $i$ 门科目在第 $j$ 周需要完成一份难度为 $a_{i, j}$ 的作业。注意，整张表格中所有的难度值均**两两不同**。 Vus 将一周的**难度**定义为该周所有科目作业难度的总和。 Vus 假期没有休息够，所以他希望至少学期初不要学得太累。幸运的是，今年学生被允许调整自己的学习计划。Vus 可以执行以下操作至多 $k$ 次：选择一门科目 $i$ 和不同的两周 $j_1$ 与 $j_2$，然后交换这门科目在这两周的作业。于是，在表格中，$a_{i, j_1}$ 与 $a_{i, j_2}$ 交换位置。 Vus 的目标是让第一周的难度尽可能小。如果有多种方式达到这一点，他希望让第二周的难度尽可能小。如果仍有多种方式，则让第三周的难度尽可能小，依此类推。 更形式化地，令 $b_j$ 为第 $j$ 周的难度： $$b_j = a_{1, j} + a_{2, j} + \dots + a_{n, j}$$ Kozak Vus 希望使用不超过 $k$ 次操作，使得操作后每周难度构成的数组 $B = [b_1, b_2, \dots, b_m]$ 字典序最小。请帮助他找出这个数组。

第一行包含三个整数 $n$、$m$、$k$（$1 \le n, m \le 1000$，$0 \le k \le 10^9$）—— 行数、列数以及最大操作次数。 接下来的 $n$ 行，每行包含 $m$ 个整数 $a_{i,j}$（$1 \le a_{i,j} \le 10^6$，所有 $a_{i,j}$ 两两不同）—— 初始的表格。

输出 $m$ 个整数 —— 经过不超过 $k$ 次操作后可以得到的字典序最小的列和数组。

对于第一个样例： 由于 $k = 1$，至多可以执行一次操作。 初始的列和为： $7 + 6 + 5 = 18$， $1 + 8 + 2 = 11$， $3 + 4 + 9 = 16$。 因此初始的和数组为 $[18, 11, 16]$。 为了得到字典序最小的数组，最优做法是在第一行执行一次操作，交换数字 $7$ 和 $1$。 交换后，表格变为： 第一行：$1\ 7\ 3$， 第二行：$6\ 8\ 4$， 第三行：$5\ 2\ 9$。 此时列和为： $1 + 6 + 5 = 12$， $7 + 8 + 2 = 17$， $3 + 4 + 9 = 16$。 所得数组 $[12, 17, 16]$ 是在一次操作能够达到的所有方案中字典序最小的。 对于第二个样例： 初始的列和为： $9 + 2 + 5 = 16$， $1 + 8 + 6 = 15$， $7 + 3 + 11 = 21$， $4 + 10 + 12 = 26$。 初始的和数组为 $[16, 15, 21, 26]$。 在第一行执行一次操作，交换数字 $9$ 和 $1$，再执行第二次操作，仍然在第一行交换数字 $9$ 和 $4$。于是我们得到如下表格： $1\ 4\ 7\ 9$ $2\ 8\ 3\ 10$ $5\ 6\ 11\ 12$ 列和为 $[8, 18, 21, 31]$。 ### 计分 - （$3$ 分）：$k = n \cdot m$； - （$5$ 分）：$k = 1$，$n = 1$； - （$11$ 分）：$n = 1$； - （$13$ 分）：各行元素初始按降序排列； - （$16$ 分）：$k \le 10$； - （$11$ 分）：$m = 2$； - （$16$ 分）：$n, m \le 100$； - （$25$ 分）：无额外限制。 翻译由 DeepSeek V4 Pro 完成