给定一个 n×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≤2500
数据保证所有出现的数不超过 109
- 进阶:二分做法优化输入后可以通过,但不妨试试 O(nm) 做法