P9457 [Beginner Contest #14] Magical Girl Fusu (Hard Version)

You are given a numeric matrix with $n$ rows and $m$ columns. The number in row $i$ and column $j$ is called $a_{i,j}$. Fusu can cast magic any number of times. Each time she casts the magic, **every** number in the matrix is decreased by $1$. Now Fusu wants to know: at least how many times does she need to cast the magic so that there exist at least $k$ positions $(x, y)$ in the matrix such that $a_{x, y}$ is greater than or equal to the sum of the elements in its row and its column. Formally, you need to compute the minimum number of magic casts such that after casting, there exist at least $k$ positions $(x, y)$ satisfying $a_{x, y} \geq \sum \limits _{i = 1}^n a_{i,y} + \sum \limits _{i = 1}^m a_{x,i}$.

The first line contains three integers, representing the number of rows $n$, the number of columns $m$, and the required number of positions $k$. Then follow $n$ lines, each containing $m$ integers. The $j$-th integer in the $i$-th line represents the initial value of $a_{i,j}$.

Output one line with one integer, representing the answer.

### Sample 1 Explanation After casting the magic $3$ times, the matrix becomes $$\begin{matrix}-2 & -1 & 0\\1& 2&3\\\end{matrix}$$ Then $a_{1,1} = -2 > (-1) + (-3) = \sum\limits_{i =1}^n a_{i,1} + \sum\limits_{i = 1}^m a_{1, i}$. ### Constraints - For $100\%$ of the testdata, it is guaranteed that $1 \leq n, m \leq 3 \times 10^3$, $1 \leq k \leq n \times m$, $0 \leq a_i \leq 10^{11}$. ### Hint **Please use a reasonable input method to avoid TLE.** Translated by ChatGPT 5