新年的问题（数据加强版）

题目描述

给定一个 $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)$ 做法