Description

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.

Input Format

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 Format

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

2 3 1
1 2 4
2 4 1

1

3 4 2
1 5 6 6
8 3 4 3
6 8 6 3

3

Hint

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