CF2248F.Matrix Elimination

You are given an integer $k$ and a matrix $v$ with $n$ rows and $m$ columns. The element in row $i$ and column $j$ is denoted by $v_{i,j}$.

A cell $(x, y)$ is called a peak if its value is greater than or equal to the sum of the values in all other cells in row $x$ and column $y$. Formally, $(x, y)$ is a peak if

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

You may perform the following operation any number of times (possibly zero):

• Choose four integers $x_l$, $x_r$, $y_l$, and $y_r$ ($1 \le x_l \le x_r \le n$, $1 \le y_l \le y_r \le m$).
• Subtract $1$ from $v_{i,j}$ for every $x_l \le i \le x_r$ and $y_l \le j \le y_r$.

Find the minimum number of operations required to obtain a matrix with at least $k$ peaks.

给你一个整数 $k$ 和一个具有 $n$ 行 $m$ 列的矩阵 $v$。第 $i$ 行第 $j$ 列的元素记为 $v_{i,j}$。

若某个单元格 $(x, y)$ 的值大于或等于其所在行 $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$）；
• 对所有满足 $x_l \le i \le x_r$ 且 $y_l \le j \le y_r$ 的单元格 $(i, j)$，将 $v_{i,j}$ 减 $1$。

求使矩阵中至少包含 $k$ 个峰点所需的最少操作次数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains three integers $n$, $m$, and $k$ ($1 \le n, m \le 10^5$, $1 \le k \le n \cdot m$, $n \cdot m \le 10^5$) — the number of rows, the number of columns, and the required number of peaks.

The $i$-th of the next $n$ lines contains $m$ integers $v_{i,1}, v_{i,2}, \ldots, v_{i,m}$ ($-10^9 \le v_{i,j} \le 10^9$).

It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例数量 $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$），分别表示行数、列数以及所需的峰的数量。

接下来的 $n$ 行中，第 $i$ 行包含 $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$。

For each test case, output a single integer — the minimum number of operations required to obtain at least $k$ peaks.

If there is no solution, print a single integer $-1$.

对于每个测试用例，输出一个整数——得到至少 $k$ 个峰值所需的最少操作次数。

若无解，则输出整数 $-1$。

For the first test case, you can perform the following two operations:

• choose $(x_l, x_r, y_l, y_r) = (1, 3, 2, 3)$;
• choose $(x_l, x_r, y_l, y_r) = (2, 3, 1, 3)$.

After these operations, the matrix will be:

$\color{green}{-1}$

$-31$

$\color{green}{6}$

$5$

$\color{green}{-5}$

$\color{green}{20}$

$\color{green}{0}$

$\color{green}{-20}$

$\color{green}{14}$

The seven peaks are highlighted in green. For example:

• The cell $(1, 1)$ is a peak because $-1 \ge 5 + 0 - 31 + 6 = -20$;
• The cell $(3, 1)$ is a peak because $0 \ge -20 + 14 - 1 + 5 = -2$;
• The cell $(2, 1)$ is not a peak because $5 \lt -5 + 20 - 1 + 0 = 14$.

It can be shown that fewer than two operations cannot create seven peaks, so the answer is $2$.

In the eighth test case, the only cell has value $-5$. A cell in a $1 \times 1$ matrix is a peak if and only if its value is non-negative. Since every operation only decreases its value, it is impossible to make it a peak.

For the last test case, both cells are peaks exactly when their values are equal. Therefore, the first cell must be decreased from $10^9$ to $-10^9$, which requires $2 \cdot 10^9$ operations.

对于第一个测试用例，你可以执行以下两次操作：

• 选择 $(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$ 次操作。