New Year's Problem (Enhanced Version)

Problem Description

Given an $n \times m$ matrix, you must choose exactly one number from each column, such that among these chosen numbers there exist two that are in the same row. Maximize the minimum of these $m$ chosen numbers, and output that value.

Input Format

The first line contains two positive integers $n, m$.

The next $n$ lines each contain $m$ positive integers.

Output Format

One positive integer.

Sample Input

2 2
1 2
3 4

Sample Output

3

Sample Explanation

$m = 2$, which requires choosing from at most $2 - 1 = 1$ row, i.e. only one row can be chosen. Choosing the first row gives $1, 2$ with minimum $1$; choosing the second row gives $3, 4$ with minimum $3$. So the answer is $3$.

Constraints

$2 < n, m \le 2500$.

All numbers appearing are at most $10^9$.

• Further note: A binary search solution can pass after optimizing input, but you may also try an $O(nm)$ approach.