Minimum k-th Largest in Permutation Selection

Given an \(n \times m\) matrix \(A\) (with \(n \le m\)), you are required to select \(n\) numbers from the matrix such that no two selected numbers come from the same row or the same column. Let the \(n\) selected numbers be sorted in non‐increasing order. Your task is to determine the minimum possible value of the \(k\)-th largest number among those selected numbers.

Clarification: If you denote the selected numbers as \(x_1, x_2, \dots, x_n\) and sort them so that \(x_1 \ge x_2 \ge \dots \ge x_n\), you need to minimize \(x_k\) over all valid selections.

Hint: A common approach is to use binary search over the possible values together with a bipartite matching check on a graph where an edge between row \(i\) and column \(j\) exists if \(A_{i,j} \le X\). The condition to check for a given candidate \(X\) is whether you can select at least \(k\) cells with values \(\le X\) in a valid complete assignment (i.e. a permutation of columns).

Formally, for a candidate \(X\), construct a bipartite graph where an edge exists from row \(i\) to column \(j\) if \(A_{i,j} \le X\). Let the maximum matching in this graph cover \(p\) rows. If \(p \ge k\), then the candidate \(X\) is feasible.

inputFormat

The first line contains three integers \(n\), \(m\) and \(k\) (with \(n \le m\)).

Then \(n\) lines follow, each containing \(m\) integers representing the matrix \(A\). The \(j\)-th integer in the \(i\)-th line denotes \(A_{i,j}\).

outputFormat

Output a single integer, which is the minimum possible value of the \(k\)-th largest number among the chosen \(n\) numbers.

sample

2 3 1
1 2 3
4 5 6

4