F. Earnest Matrix Complement
brute force; data structures; dp; greedy; implementation; math
3, 2, 1, ... We are the — RiOI Team!— Felix & All, Special Thanks 3 Peter: Good news: My problem T311013 is approved! \(\delta\): I'm glad my computer had gone out of battery so that I wouldn't have participated in wyrqwq's round and gained a negative delta. Felix: [thumbs_up] The problem statement concerning a removed song! Aquawave: Do I mourn my Chemistry? E.Space: ahh? Trine: Bread. Iris: So why am I always testing problems? Time will pass, and we might meet again. Looking back at the past, everybody has lived the life they wanted.Aquawave has a matrix \(A\) of size \(n\times m\), whose elements can only be integers in the range \([1, k]\), inclusive. In the matrix, some cells are already filled with an integer, while the rest are currently not filled, denoted by \(-1\).You are going to fill in all the unfilled places in \(A\). After that, let \(c_{u,i}\) be the number of occurrences of element \(u\) in the \(i\)-th row. Aquawave defines the beauty of the matrix as$$$\(\sum_{u=1}^k \sum_{i=1}^{n-1} c_{u,i} \cdot c_{u,i+1}.\)\(You have to find the maximum possible beauty of \)A$$$ after filling in the blanks optimally.
The first line of input contains a single integer \(t\) (\(1 \leq t \leq 2\cdot 10^4\)) — the number of test cases. The description of test cases follows.The first line of each test case contains three integers \(n\), \(m\), and \(k\) (\(2 \leq n \leq 2\cdot 10^5\), \(2 \leq m \leq 2\cdot 10^5\), \(n \cdot m \leq 6\cdot 10^5\), \(1 \leq k \leq n\cdot m\)) — the number of rows and columns of the matrix \(A\), and the range of the integers in the matrix, respectively.Then \(n\) lines follow, the \(i\)-th line containing \(m\) integers \(A_{i,1},A_{i,2},\ldots,A_{i,m}\) (\(1 \leq A_{i,j} \leq k\) or \(A_{i,j} = -1\)) — the elements in \(A\).It is guaranteed that the sum of \(n\cdot m\) over all test cases does not exceed \(6\cdot 10^5\).
For each test case, output a single integer — the maximum possible beauty.
In the first test case, the matrix \(A\) is already determined. Its beauty is$$$\(\sum_{u=1}^k \sum_{i=1}^{n-1} c_{u,i} \cdot c_{u,i+1} = c_{1,1}\cdot c_{1,2} + c_{1,2}\cdot c_{1,3} + c_{2,1}\cdot c_{2,2} + c_{2,2}\cdot c_{2,3} + c_{3,1}\cdot c_{3,2} + c_{3,2}\cdot c_{3,3} = 1\cdot 1 + 1\cdot 1 + 2\cdot 0 + 0\cdot 1 + 0\cdot 2 + 2\cdot 1 = 4.\)\(In the second test case, one can fill the matrix as follows:\)\( \begin{bmatrix} 2 &3 &3 \\ 2 &2 &3 \end{bmatrix}, \)\(and get the value \)4\(. It can be proven this is the maximum possible answer one can get.In the third test case, one of the possible optimal configurations is:\)\( \begin{bmatrix} 1 &1 &1 \\ 1 &2 &1 \\ 1 &1 &4 \end{bmatrix}. \)\(In the fourth test case, one of the possible optimal configurations is:\)\( \begin{bmatrix} 1 &3 &2 &3 \\ 1 &3 &2 &1 \\ 3 &1 &5 &1 \end{bmatrix}. \)\(In the fifth test case, one of the possible optimal configurations is:\)\( \begin{bmatrix} 5 &5 &2 \\ 1 &8 &5 \\ 7 &5 &6 \\ 7 &7 &4 \\ 4 &4 &4 \end{bmatrix}. \)$$$