2006 「SCOI2015」小凸玩矩阵

内存限制:256 MB 时间限制:1000 ms

题目描述

小凸和小方是好朋友,小方给小凸一个 $ N \times M $($ N \leq M $)的矩阵 $ A $,要求小凸从其中选出 $ N $ 个数,其中任意两个数字不能在同一行或同一列,现小凸想知道选出来的 $ N $ 个数中第 $ K $ 大的数字的最小值是多少。

输入格式

第一行给出三个整数 $ N $、$ M $、$ K $。
接下来 $ N $ 行,每行 $ M $ 个数字,用来描述这个矩阵。

输出格式

输出选出来的 $ N $ 个数中第 $ K $ 大的数字的最小值。

样例

数据范围与提示

$ 1 \leq K \leq N \leq M \leq 250, 1 \leq A_{i, j} \leq 10 ^ 9 $

样例

样例输入 1

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

样例输出 1

3