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.

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

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

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.