Minimum Magic Casts to Satisfy Matrix Cell Condition

You are given an n × m matrix of integers. The element in the i-th row and j-th column is denoted by \(a_{i,j}\). You can cast a magic spell any number of times. Each time you cast the spell, every number in the matrix is decreased by 1.

Let \(t\) be the number of times you cast the magic spell. After \(t\) casts, the value at position \((x,y)\) becomes \(a_{x,y} - t\). For the cell \((x,y)\), define the sum of its corresponding column and row (based on the original matrix) as follows:

[ R(x,y) = \sum_{i=1}^{n}a_{i,y} + \sum_{j=1}^{m}a_{x,j}. ]

Your goal is to determine the minimum number of magic casts, \(t\), such that there exist at least k positions \((x,y)\) for which the following condition holds:

[ a_{x,y} - t \geq R(x,y) - (m+n),t. ]

Simplify the inequality as follows:

[ a_{x,y} - t \geq \left(\sum_{i=1}^{n}a_{i,y} + \sum_{j=1}^{m}a_{x,j}\right) - (m+n)t ]

Adding \( (m+n)t \) to both sides gives:

[ a_{x,y} + (m+n-1)t \geq \sum_{i=1}^{n}a_{i,y} + \sum_{j=1}^{m}a_{x,j}. ]

Thus, the condition for cell \((x,y)\) becomes:

[ t \geq \frac{\left(\sum_{i=1}^{n}a_{i,y} + \sum_{j=1}^{m}a_{x,j} - a_{x,y}\right)}{m+n-1}. ]

For each cell, define its required threshold of magic casts as:

[ t_{x,y} = \max\left(0, \left\lceil \frac{\sum_{i=1}^{n}a_{i,y} + \sum_{j=1}^{m}a_{x,j} - a_{x,y}}{m+n-1} \right\rceil\right). ]

Your task is to find the minimum integer \(t\) such that at least k cells have \(t_{x,y} \leq t\). In other words, if you compute \(t_{x,y}\) for every cell and sort them in non‐decreasing order, the answer is the \(k\)-th smallest value.

Note: It is guaranteed that \(1 \leq k \leq n \times m\).

inputFormat

The first line contains three integers, n, m, and k — the number of rows, columns, and the target number of cells, respectively.

Then follow n lines, each containing m integers. The j-th integer in the i-th line denotes \(a_{i,j}\), the element in the i-th row and j-th column of the matrix.

outputFormat

Output a single integer: the minimum number of magic casts required so that there exist at least k cells \((x,y)\) satisfying the condition \(a_{x,y} - t \geq \sum_{i=1}^{n}a_{i,y} + \sum_{j=1}^{m}a_{x,j} - (m+n)t\).

sample

2 2 1
1 2
3 4

2

</p>