Problem Description

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

Input Format

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 Format

Output one line with one integer, representing the answer.

2 3 1
1 2 3
4 5 6

3

Hint

Sample 1 Explanation

After casting the magic $3$ times, the matrix becomes

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