P1027 Mission 2 - C : The Correct Key

Problem Background

After successfully going into the capital of the USW, Radar immediately goes to the room which stores the secret files of the USW. But the room is locked. Only if Radar answer a problem right, it will open the door.

Can you help Radar solve the problem?

Problem Statement

There’re \(n\) arrays \(\left\{a_0,a_1,a_2,a_3,\cdots,a_{n-1}\right\}\), each array has \(m\) elements. We note that \(a_{x,y}\) is the \((y+1)^{th}\) element of \(a_x\).

Make \(\displaystyle \forall\ k\in[0,m),b_{k}:=\max^{n-1}_{i=0}\max\left\{a_{i,k},a_{k, \left(i\ \bmod\ m\right)}\right\}\).

Please figure out \(\displaystyle\max^{m-1}_{i=0}b_{i}\).

Input

\(n\ m\)

\(a_{1,1}\ a_{1,2}\ \cdots\ a_{1,m}\)

\(a_{2,1}\ a_{2,2}\ \cdots\ a_{2,m}\)

\(\ \ \vdots\ \ \ \ \ \ \vdots\ \ \ \ \ \ \vdots\ \ \ \ \ \ \vdots\)

\(a_{n,1}\ a_{n,2}\ \cdots\ a_{n,m}\)

Output

\(\displaystyle\large\max^{m}_{i=1}b_{i}\)

Constraints

• For \(30\) points:

  • \(1 \le m \le n \le 8\).

• For \(100\) points:

  • \(1 \le n \le 3 \times 10^5\).
  • \(1 \le m \le 8\).
  • \(m \le n\).
  • \(a_{x,y} \le 10^9(1 \le x \le n, 1 \le y \le m)\).