题目描述

题目译自 European Girls' Olympiad in Informatics 2025 Day2 T3. IMO

国际数学奥林匹克（IMO）是一项面向高中生的数学竞赛，每年举行一次。2025 年的 IMO 与 EGOI 同期举行。当你阅读本文时，IMO 的两个比赛日已经结束，评分工作可能也接近完成。与 EGOI 这样的编程竞赛不同，IMO 的评分是手工完成的，这是一个漫长而艰辛的过程。

今年的 IMO 共有 $M$ 道题目（编号从 $0$ 到 $M-1$），每道题目最高得分为 $K$ 分。共有 $N$ 名参赛者参加比赛。第 $i$ 名参赛者在题目 $j$ 上的得分为 $a_{i,j}$，其中 $a_{i,j}$ 是一个介于 $0$ 到 $K$ 之间的整数（包含两端）。参赛者的排名由每个参赛者的总分决定，平局时按参赛者编号打破僵局。更正式地说，参赛者 $x$ 的排名高于参赛者 $y$，如果：

• 参赛者 $x$ 的总分高于参赛者 $y$ 的总分，
• 或者他们的总分相同且 $x < y$。

为了发布最终排名，组织者需要公布一些 $a_{i,j}$ 的值。如果某个值未公布，则仅知道它是一个介于 $0$ 到 $K$ 之间的整数（包含两端）。

组织者希望尽可能少地公布 $a_{i,j}$ 的值。同时，他们需要确保每个人都知道正确的最终排名。换句话说，他们必须公布一组值，使得唯一符合这些值的排名是正确的排名。

找出最小的 $S$，使得可以通过公布 $S$ 个 $a_{i,j}$ 的值来唯一确定参赛者的完整排名。

输入格式

第一行包含三个整数 $N, M, K$：分别表示参赛者数量、题目数量和题目的最高得分。

接下来有 $N$ 行，其中第 $i$ 行包含 $a_{i,j}$。也就是说，第一行包含 $a_{0,0}, a_{0,1}, \ldots, a_{0,M-1}$，第二行包含 $a_{1,0}, a_{1,1}, \ldots, a_{1,M-1}$，依此类推。

输出格式

输出一个整数 $S$，表示可以公布的最小分数数量，使得最终排名被唯一确定。

4 6 7
7 7 0 2 7 0
7 3 0 7 2 1
7 0 0 7 0 0
7 7 7 7 7 1

20

在第一个样例中，可以按以下方式公布 $20$ 个分数：

$$\begin{array}{|c|c|c|c|c|c|} \hline 7 & 7 & 0 & \bullet & 7 & \bullet \\ \hline 7 & 3 & 0 & 7 & 2 & 1 \\ \hline \bullet & 0 & 0 & \bullet & 0 & 0 \\ \hline 7 & 7 & 7 & 7 & 7 & 1 \\ \hline \end{array} $$

在这里，第三名参赛者的总分已知在 $0$ 到 $14$ 之间，这肯定低于其他任何分数。可以证明，无法公布少于 $20$ 个分数。例如，如果我们隐藏第三名参赛者的一个零分，那么该参赛者的总分可能高达 $21$。这是一个问题，因为第二名参赛者的总分为 $20$，但应保证排名高于第三名参赛者。

第一个样例满足子任务 $5, 6$ 的限制条件。

2 1 1
1
0

1

在第二个示例中，我们可以只公布第一名参赛者的唯一分数，或者只公布第二名参赛者的唯一分数（但不能两者都公布）。如果我们只公布第一名参赛者的分数，那么我们知道第一名参赛者的总分为 $1$。这意味着即使第二名参赛者也有 $1$ 分，第一名参赛者仍会排名更高，因为他们的编号更小。同样，如果我们只公布第二名参赛者的分数，我们知道他们的得分为零，这意味着无论第一名参赛者的得分如何，他们都将排名更高。

第二个样例满足子任务 $2, 3, 4, 5, 6$ 的限制条件。

2 2 7
7 4
7 0

2

第三个样例满足子任务 $2, 3, 5, 6$ 的限制条件。

2 2 1
0 1
1 0

2

第四个样例满足所有子任务的限制条件。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 20000$。
• $1 \leq M \leq 100$。
• $1 \leq K \leq 100$。
• 对于每个 $i, j$（其中 $0 \leq i \leq N-1$ 且 $0 \leq j \leq M-1$），$0 \leq a_{i,j} \leq K$。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$10$	$N=M=2$ 且 $K=1$
$2$	$13$	$N=2$
$3$	$10$	$N \cdot M \leq 16$
$4$	$18$	$K=1$
$5$	$21$	$N \leq 10000$ 且 $M, K \leq 10$
$6$	$28$	无附加限制