F. Устранение матрицы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано целое число $$$k$$$ и матрица $$$v$$$ из $$$n$$$ строк и $$$m$$$ столбцов. Элемент в строке $$$i$$$ и столбце $$$j$$$ обозначается как $$$v_{i,j}$$$.

Ячейка $$$(x, y)$$$ называется пиком, если её значение больше или равно сумме значений во всех остальных ячейках строки $$$x$$$ и столбца $$$y$$$. Формально, $$$(x, y)$$$ является пиком тогда и только тогда, когда

$$$$$$ v_{x,y} \ge \sum_{\substack{1 \le i \le n \\i \neq x}} v_{i,y} + \sum_{\substack{1 \le j \le m \\j \neq y}} v_{x,j}. $$$$$$

Вы можете выполнять следующую операцию любое количество раз (возможно, ноль):

  • Выберите четыре целых числа $$$x_l$$$, $$$x_r$$$, $$$y_l$$$ и $$$y_r$$$ ($$$1 \le x_l \le x_r \le n$$$, $$$1 \le y_l \le y_r \le m$$$).
  • Вычтите $$$1$$$ из $$$v_{i,j}$$$ для всех $$$x_l \le i \le x_r$$$ и $$$y_l \le j \le y_r$$$.

Найдите минимальное количество операций, необходимое, чтобы получить матрицу, в которой есть хотя бы $$$k$$$ пиков.

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

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

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le n, m \le 10^5$$$, $$$1 \le k \le n \cdot m$$$, $$$n \cdot m \le 10^5$$$) — количество строк, количество столбцов и требуемое количество пиков.

$$$i$$$-я из следующих $$$n$$$ строк содержит $$$m$$$ целых чисел $$$v_{i,1}, v_{i,2}, \ldots, v_{i,m}$$$ ($$$-10^9 \le v_{i,j} \le 10^9$$$).

Гарантируется, что сумма значений $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — минимальное количество операций, необходимое, чтобы получить хотя бы $$$k$$$ пиков.

Если решения не существует, выведите одно целое число $$$-1$$$.

Пример
Входные данные
16
3 3 7
-1 -30 7
6 -3 22
1 -18 16
3 1 2
100000000
300000000
200000000
1 3 1
2 3 4
1 3 1
1 2 3
1 2 2
5 7
5 2 8
531959596 -61416172
425363565 672913308
981527099 451180253
-161687136 898803495
-388356105 897723313
1 1 1
0
1 1 1
-5
1 4 3
-8 -4 4 -11
1 9 5
-12 -4 -13 9 -1 -15 6 -15 -4
1 3 3
-12 -15 8
1 5 5
10 8 -4 0 -4
1 3 3
12 9 -1
1 3 3
-14 11 -6
1 6 6
-1 0 15 3 1 -14
1 2 2
1000000000 -1000000000
Выходные данные
2
100000000
1
0
2
734592698
0
-1
0
0
11
6
12
11
7
2000000000
Примечание

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

  • выбрать $$$(x_l, x_r, y_l, y_r) = (1, 3, 2, 3)$$$;
  • выбрать $$$(x_l, x_r, y_l, y_r) = (2, 3, 1, 3)$$$.

После этих операций матрица будет такой:

$$$\color{green}{-1}$$$$$$-31$$$$$$\color{green}{6}$$$
$$$5$$$$$$\color{green}{-5}$$$$$$\color{green}{20}$$$
$$$\color{green}{0}$$$$$$\color{green}{-20}$$$$$$\color{green}{14}$$$

Семь пиков выделены зелёным цветом. Например:

  • Ячейка $$$(1, 1)$$$ является пиком, потому что $$$-1 \ge 5 + 0 - 31 + 6 = -20$$$;
  • Ячейка $$$(3, 1)$$$ является пиком, потому что $$$0 \ge -20 + 14 - 1 + 5 = -2$$$;
  • Ячейка $$$(2, 1)$$$ не является пиком, потому что $$$5 \lt -5 + 20 - 1 + 0 = 14$$$.

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

В восьмом наборе входных данных единственная ячейка имеет значение $$$-5$$$. Ячейка в матрице $$$1 \times 1$$$ является пиком тогда и только тогда, когда её значение неотрицательно. Поскольку каждая операция только уменьшает её значение, сделать её пиком невозможно.

Для последнего набора входных данных обе ячейки являются пиками тогда и только тогда, когда их значения равны. Следовательно, первую ячейку нужно уменьшить с $$$10^9$$$ до $$$-10^9$$$, что требует $$$2 \cdot 10^9$$$ операций.