题目描述

国际数学奥林匹克（IMO）是一项面向高中生的数学竞赛，每年举办一次。2025 年的 IMO 正好与 EGOI 同时进行。当你读到这道题时，两天的 IMO 正赛已经结束，评分工作也大概接近尾声。与 EGOI 这样的程序设计竞赛不同，IMO 的评分完全依靠人工完成，这是一项漫长而繁琐的工作。

今年的 IMO 包含 $M$ 道题目（编号为 $0$ 到 $M-1$），每道题的满分为 $K$ 分。有 $N$ 名选手参加比赛。第 $i$ 名选手在第 $j$ 道题上的得分为 $a_{i,j}$，其中 $a_{i,j}$ 是 $0$ 到 $K$ 之间的整数（包含 $0$ 和 $K$）。选手的排名由总分决定，若总分相同，则按选手编号（索引）从小到大排名。更正式地说，若满足以下条件之一，则选手 $x$ 的排名高于选手 $y$：

• 选手 $x$ 的总分大于选手 $y$ 的总分，
• 或者两人总分相同且 $x < y$。

为了公布最终排名，主办方需要公开部分 $a_{i,j}$ 的值。若某个值未公开，则只知道它是 $0$ 到 $K$ 之间的某个整数。

主办方希望尽量少地公开 $a_{i,j}$ 的值。同时，他们必须确保所有人都能唯一确定最终排名。换言之，主办方需要公开一组 $a_{i,j}$，使得与这些信息相符的排名只有唯一的正确排名。

请你求出最小的 $S$，使得最多只需公开 $S$ 个 $a_{i,j}$，就能唯一确定所有选手的完整排名。

输入格式

第一行包含三个整数 $N$、$M$ 和 $K$，分别表示选手数、题目数和每题的最高分。

接下来 $N$ 行，每行 $M$ 个整数，第 $i$ 行为 $a_{i,0}, a_{i,1}, \ldots, a_{i,M-1}$。

输出格式

输出一个整数 $S$，表示唯一确定最终排名所需公开的最少分数个数。

输入输出样例 #1

输入 #1

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

输出 #1

20

输入输出样例 #2

输入 #2

2 1 1
1
0

输出 #2

1

输入输出样例 #3

输入 #3

2 2 7
7 4
7 0

输出 #3

2

输入输出样例 #4

输入 #4

2 2 1
0 1
1 0

输出 #4

2

说明/提示

样例说明

在第一个样例中，只需公开 20 个分数即可，方案如下：

7		0	$\cdot$	7	$\cdot$
7	3	0	7	2	1
$\cdot$	0		$\cdot$	0
7					1

此时，第三名选手的总分已知在 $0$ 到 $14$ 之间，肯定低于其他所有人。可以证明，不能再少公开一个分数。例如，如果隐藏第三名选手的某个 $0$，那么他的总分最高可达 $21$，这就可能导致第二名选手的总分 $20$ 无法保证排在第三名前面。

第一个样例满足测试组 5 和 6 的约束。

在第二个样例中，只需公开第一名选手的唯一分数，或者只公开第二名选手的唯一分数（不可都公开）。如果只公开第一名选手的分数，就能确定他总分为 $1$，即使第二名选手分数也是 $1$，第一名选手编号更小，排名更高。类似地，如果只公开第二名选手的分数，可知他总分为 $0$，无论第一名得多少分，第一名都排名更高。

第二个样例满足测试组 2、3、4、5、6 的约束。

第三个样例满足测试组 2、3、5、6 的约束。

第四个样例满足所有测试组的约束。

约束与评分

• $2 \leq N \leq 20000$
• $1 \leq M \leq 100$
• $1 \leq K \leq 100$
• $0 \leq a_{i,j} \leq K$，对所有 $0 \leq i \leq N-1$，$0 \leq j \leq M-1$

你的解答将在一组测试组上进行评测，每组包含若干测试用例。要获得该测试组的分数，你需要通过该测试组的所有测试用例。

测试组	分值	限制条件
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	无额外限制