该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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)\).