F. Искренний матричный комплемент
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
3, 2, 1, ... We are the — RiOI Team!
— Felix & All, Special Thanks 3
  • Питер: Хорошие новости! Моя задача T311013 была одобрена!
  • $$$\delta$$$: Я рад, что у моего компьютера разрядилась батарея, иначе я бы поучаствовал в раунде wyrqwq и получил бы отрицательную дельту.
  • Феликс: [thumbs_up] Условие задачи про удалённую песню!
  • Аквавейв: Нужно ли мне оплакивать свою химию?
  • Е.Космос: что?
  • Трайн: Хлеб.
  • Ирис: И почему же я всегда только тестирую задачи?

Пройдет время, и мы, возможно, встретимся снова. Оглядываясь назад на прошлое, можно сказать, что каждый прожил ту жизнь, которую хотел.

У Аквавейва есть матрица $$$A$$$ размера $$$n\times m$$$, элементы которой могут быть только целыми числами в диапазоне $$$[1, k]$$$ включительно. В матрице некоторые ячейки уже заполнены целым числом, в то время как остальные в данный момент не заполнены и обозначаются числом $$$-1$$$.

Вы собираетесь заполнить все незаполненные ячейки в $$$A$$$. После этого пусть $$$c_{u,i}$$$ будет обозначать количество вхождений элемента $$$u$$$ в $$$i$$$-ю строку. Аквавейв определяет красоту матрицы следующим образом:

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

Вы должны найти максимально возможную красоту $$$A$$$ после оптимального заполнения пробелов.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 2\cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$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$$$) — количество строк и столбцов матрицы $$$A$$$ и диапазон целых чисел в матрице соответственно.

Затем следуют $$$n$$$ строк, $$$i$$$-я строка содержит $$$m$$$ целых числа $$$A_{i,1},A_{i,2},\ldots,A_{i,m}$$$ ($$$1 \leq A_{i,j} \leq k$$$ или $$$A_{i,j} = -1$$$) — элементы в $$$A$$$.

Гарантируется, что сумма $$$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
Выходные данные
4
4
10
10
8
102
93
58
13
Примечание

В первом наборе входных данных матрица $$$A$$$ уже определена. Её красота равняется

$$$$$$\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.$$$$$$

Во втором наборе входных данных можно заполнить матрицу следующим образом:

$$$$$$ \begin{bmatrix} 2 &3 &3 \\ 2 &2 &3 \end{bmatrix}, $$$$$$

и получить значение $$$4$$$. Можно доказать, что это максимально возможный ответ, который можно получить.

В третьем наборе входных данных одной из возможных оптимальных конфигураций является:

$$$$$$ \begin{bmatrix} 1 &1 &1 \\ 1 &2 &1 \\ 1 &1 &4 \end{bmatrix}. $$$$$$

В четвертом наборе входных данных одной из возможных оптимальных конфигураций является:

$$$$$$ \begin{bmatrix} 1 &3 &2 &3 \\ 1 &3 &2 &1 \\ 3 &1 &5 &1 \end{bmatrix}. $$$$$$

В пятом наборе входных данных одной из возможных оптимальных конфигураций является:

$$$$$$ \begin{bmatrix} 5 &5 &2 \\ 1 &8 &5 \\ 7 &5 &6 \\ 7 &7 &4 \\ 4 &4 &4 \end{bmatrix}. $$$$$$