P4251 [SCOI2015] Xiao Tu Plays with Matrices

Xiao Tu and Xiao Fang are good friends. Xiao Fang gave Xiao Tu an $n \times m$ ($n \leq m$) matrix $A$, and asks Xiao Tu to choose $n$ numbers from the matrix such that no two chosen numbers are in the same row or the same column. Now Xiao Tu wants to know the minimum possible value of the $k$-th largest number among the $n$ chosen numbers.

The first line contains 3 integers $n$, $m$, $k$. Then follow $n$ lines, each containing $m$ numbers. In the $i$-th line, the $j$-th number denotes the element $A_{i,j}$ at row $i$ and column $j$ of the matrix.

Output one line: the minimum possible value of the $k$-th largest number among the $n$ chosen numbers.

For $20$% of the testdata, $1 \leq n \leq m \leq 9$. For $40$% of the testdata, $1 \leq n \leq m \leq 22$, $1 \leq n \leq 12$. For $100$% of the testdata, $1 \leq k \leq n \leq m \leq 250$, $1 \leq A_{i,j} \leq 10^9$. Translated by ChatGPT 5