F. 真诚矩阵补全

时间限制：每个测试点 $5$ 秒 内存限制：每个测试点 $512$ 兆字节

3，2，1……我们是——RiOI Team！ ——Felix & 全体成员，特别致谢 3

Peter：好消息！我的题目 T311013 通过审核了！ δ：真庆幸我的电脑没电了，这样我就不用参加 wyrqwq 的比赛并掉分了。 Felix：[点赞] 是关于下架歌曲的题目！ Aquawave：我该为我的化学伤心吗？ E.Space：啊？ Trine：面包。 Iris：所以为什么总是我在测题？

时光流逝，我们或许会再次相遇。回望过去，每个人都曾活成自己想要的样子。

Aquawave 有一个大小为 $n \times m$ 的矩阵 $A$ ，矩阵中的元素只能是范围 $[1, k]$ 内的整数。矩阵中，一些格子已经填入了整数，其余未填充的格子用 $-1$ 表示。

你需要将所有未填充的格子填满。填完之后，定义 $c_{u,i}$ 表示第 $i$ 行中元素 $u$ 出现的次数。

Aquawave 定义矩阵的美观度为：

$$\sum_{u=1}^{k} \sum_{i=1}^{n-1} c_{u,i} \cdot c_{u,i+1} $$

你需要求出：在最优填充下，矩阵能达到的最大美观度。

输入格式

每个测试包含多组测试数据。第一行一个整数 $t$ （ $1 \le t \le 2 \cdot 10^4$ ）—— 测试数据组数。

每组测试数据：

第一行三个整数 $n, m, k$ （ $2 \le n \le 2 \cdot 10^5$ ， $2 \le m \le 2 \cdot 10^5$ ， $n \cdot m \le 6 \cdot 10^5$ ， $1 \le k \le n \cdot m$ ）分别表示矩阵的行数、列数，以及元素的值域。
接下来 $n$ 行，每行 $m$ 个整数 $A_{i,1}, A_{i,2}, \dots, A_{i,m}$ 。每个数满足 $1 \le A_{i,j} \le k$ 或 $A_{i,j} = -1$ 。

保证所有测试用例的 $n \cdot m$ 之和不超过 $6 \cdot 10^5$ 。

输出格式

对于每组测试数据，输出一行一个整数，表示最大可能的美观度。

样例输入

9
3 3 3
1 2 2
3 1 3
3 2 1
2 3 3
-1 3 3
2 2 -1
3 3 6
-1 -1 1
1 2 -1
-1 -1 4
3 4 5
1 3 2 3
-1 -1 2 -1
3 1 5 1
5 3 8
5 -1 2
1 8 -1
-1 5 6
7 7 -1
4 4 4
6 6 5
-1 -1 5 -1 -1 -1
-1 -1 -1 -1 2 -1
-1 1 3 3 -1 -1
-1 1 -1 -1 -1 4
4 2 -1 -1 -1 4
-1 -1 1 2 -1 -1
6 6 4
-1 -1 -1 -1 1 -1
3 -1 2 2 4 -1
3 1 2 2 -1 -1
3 3 3 3 -1 2
-1 3 3 -1 1 3
3 -1 2 2 3 -1
5 5 3
1 1 3 -1 1
2 2 -1 -1 3
-1 -1 -1 2 -1
3 -1 -1 -1 2
-1 1 2 3 -1
6 2 7
-1 7
-1 6
7 -1
-1 -1
-1 -1
2 2

样例输出

样例解释

第一个测试用例：矩阵已经完全填充，其美观度计算如下：

$$\begin{align*} \sum_{u=1}^{k}\sum_{i=1}^{n-1} c_{u,i} \cdot c_{u,i+1} &= c_{1,1}\!c_{1,2} + c_{1,2}\!c_{1,3} \\ &+ c_{2,1}\!c_{2,2} + c_{2,2}\!c_{2,3} \\ &+ c_{3,1}\!c_{3,2} + c_{3,2}\!c_{3,3} \\ &= 1\!\cdot\!1 + 1\!\cdot\!1 + 2\!\cdot\!0 + 0\!\cdot\!1 + 0\!\cdot\!2 + 2\!\cdot\!1 = 4. \end{align*} $$

#CF2053F. 真诚矩阵补全

真诚矩阵补全