[SCOI2015] 小凸玩矩阵
题目描述
小凸和小方是好朋友,小方给了小凸一个 $n$ × $m$ $(n \leq m)$ 的矩阵 $A$,并且要求小凸从矩阵中选出 $n$ 个数,其中任意两个数都不能在同一行或者同一列。现在小凸想知道,选出的 $n$ 个数中第 $k$ 大的数的最小值是多少。
输入输出格式
输入格式
第 $1$ 行读入 $3$ 个整数 $n, m, k$。
接下来 $n$ 行,每一行有 $m$ 个数字,第 $i$ 行第 $j$ 个数字代表矩阵中第 $i$ 行第 $j$ 列的元素 $A_{i,j}$。
输出格式
输出包含一行,为选出的 $n$ 个数中第 $k$ 大数的最小值。
输入输出样例
输入样例 #1
2 3 1
1 2 4
2 4 1
输出样例 #1
1
输入样例 #2
3 4 2
1 5 6 6
8 3 4 3
6 8 6 3
输出样例 #2
3
说明
对于 $20$% 的数据, $1 \leq n \leq m \leq 9$
对于 $40$% 的数据, $1 \leq n \leq m \leq 22, 1 \leq n \leq 12$
对于 $100$% 的数据, $1 \leq k \leq n \leq m \leq 250, 1 \leq A_{i,j} \leq 10^9$