Minimum Magic Releases

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

After casting the magic spell \(t\) times, the element \(a_{i,j}\) becomes \(a_{i,j} - t\). The sums of the i^th row and the j^th column become \(\sum_{k=1}^{m}a_{i,k} - m\,t\) and \(\sum_{k=1}^{n}a_{k,j} - n\,t\) respectively. We say a position \((x,y)\) is valid if after casting the spells it satisfies the following inequality: \[ a_{x,y} - t \ge \left(\sum_{i=1}^{n} a_{i,y} - n\,t\right) + \left(\sum_{j=1}^{m} a_{x,j} - m\,t\right). \] Simplifying the inequality, we get: \[ a_{x,y} - t \ge \sum_{i=1}^{n} a_{i,y} + \sum_{j=1}^{m} a_{x,j} - (n+m)t, \] which is equivalent to \[ a_{x,y} - \left(\sum_{i=1}^{n} a_{i,y} + \sum_{j=1}^{m} a_{x,j}\right) + (n+m-1)t \ge 0. \] Thus, for each position \((x,y)\), the condition is satisfied if: \[ t \ge \frac{\sum_{i=1}^{n} a_{i,y} + \sum_{j=1}^{m} a_{x,j} - a_{x,y}}{n+m-1}. \] Note that since \(t\) must be an integer, we take the ceiling of the right-hand side. In other words, for each position \((x,y)\) define the required number of magic spells 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}}{n+m-1} \right\rceil\right). \] Your task is to find the minimum integer \(t\) such that there exist at least \(k\) positions \((x,y)\) with \(t_{x,y} \le t\). Equivalently, if you compute \(t_{x,y}\) for every position, the answer is the \(k\)-th smallest value among them.

Input Format: The first line contains three integers \(n, m, k\) \((1 \le n, m \le 10^3,\ 1 \le k \le nm)\). The next \(n\) lines each contain \(m\) integers representing the matrix.

Output Format: Output a single integer, the minimum number of magic releases required.

inputFormat

The first line contains three integers \(n, m, k\). \(n\) denotes the number of rows and \(m\) denotes the number of columns of the matrix, and \(k\) is the minimum number of positions that must satisfy the condition after applying the magic. The following \(n\) lines each contain \(m\) space-separated integers representing the matrix \(a\).

outputFormat

Output a single integer, representing the minimum number of magic releases required such that there exist at least \(k\) positions \((x, y)\) satisfying the condition.

sample

2 2 1
1 2
3 4

2