ml1 | matgame

John is playing a game on a square matrix of dimensions $N\times N$. The rows and the columns of the matrix are numbered from $1$ to $N$. Cell $(i,j)$ is the cell located in the $j$-th column of the $i$-th row. The matrix contains integers in each cell, specifically, the number written in cell $(i,j)$ is $a_{i,j}$.

The game consists of a sequence of moves of the form:

• Select a cell $(i,j)$.
• The score of the move is the value $a_{i,j}$ written in cell $(i,j)$.
• Remove the $i$-th row and the $j$-th column from the matrix.
• Repeat the same process until the matrix becomes empty.

The score of the game is defined as the minimum of the scores of the moves. John asks you to determine the maximum possible score of a game that can be played on the given matrix.

Input data

The first line of input contains $N$, the number of rows and columns of the matrix.

Each of the next $N$ lines contains $N$ numbers. The $j$-th number in the $i$-th line is the value $a_{i,j}$, i.e., the number written in cell $(i,j)$.

Output data

Output a single number, representing the maximal possible score achievable in a game.

Constraints and Clarifications

• $1 \leq N \leq 1 \ 000$.
• $0\leq a_{i,j}\leq 10^{9}$ for each $i = 1\ldots N$ and $j = 1\ldots N$.

Example

stdin

3
8 0 7
5 6 9
1 7 9

stdout

7

Explanation

In the sample case, one possible optimal way of playing the game is as follows:

• First, select cell $(1, 1)$ with the value $8$, and remove the first row and the first column. The matrix becomes this:

• Then, select the cell $(2, 1)$ of this new matrix with the value $7$, and remove the second row and the first column. The matrix will consist of a single value $9$.
• Finally, select the single value $9$ in the matrix, and remove it so that the matrix becomes empty.

The score of the game is the minimum of the scores of the moves, which is $7$.