给定一个 $n\times m$ 的矩阵,要求在每列中恰好选择一个数,并且这些数里面存在两个数在同一行,要求使这 $m$ 个数的最小值最大,输出该值。
输入格式
第一行输入两个正整数 $n,m$
接下来 $n$ 行,每行 $m$ 个正整数
输出格式
一个正整数
样例输入
2 2
1 2
3 4
样例输出
3
样例解释
$m=2$,要求选择不超过 $2-1=1$ 行,即只能选择一行,选择第一行即 $1,2$,最小值为 $1$,选择第二行即 $3,4$,最小值为 $3$,所以答案为 $3$
数据范围
$2 < n , m \leq 2500 $
数据保证所有出现的数不超过 $10^9$
- 进阶:二分做法优化输入后可以通过,但不妨试试 $O(nm)$ 做法