Engage the Medical Workers

题号：NC205093
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

The medical team from Bitland has arrived at their destination --- a city named Matrix which is suffering from COVID-19. Now they are going to distribute the manpower to the place in need properly.

The Matrix city has only horizontal and vertical roads, dividing the city into $n*n$ separated blocks. That is, you can consider the blocks in this city form a real matrix of $n$ rows and $n$ columns!

The COVID-19 is now spreading among the blocks, which has infected many innocent people. xyjj, the captain of the team, now needs to consider how may medical workers should be sent to each block. If we note the number of patients in the blocks of $i-th$ row and $j-th$ as $A_{i,j}$ , and the number of medical workers sent to that block as $B_{i,j}$ , the basic rule of the arrangement will be as follows:

If $A_{i,j} \lt A_{i,j'}$ , then $B_{i,j} \lt B_{i,j'}$ ;
If $A_{i,j} \lt A_{i',j}$ , then $B_{i,j} \lt B_{i',j}$ ;
If $A_{i,j}=A_{i',j'}$ , then $B_{i,j}=B_{i',j'}$ .

Here $i,i'$ means any different rows and $j,j'$ means any different column.

Because the life expenses of the workers are covered by the local block, xyjj hopes that the maximum number of workers to be sent to each block to be minimum (That is, minimize the $max\{B_{i,j}\}$ among all the blocks) , so there will be less financial pressure for that block.

xyjj is too busy to solve this problem, can you help him?

输入描述:

The first line contains an integer $n(1 \le n \le 1000)$ , indicating that Matrix city has $n$ rows and $n$ columns of blocks.

In the next $n$ lines, each line has $n$ numbers. The $j$ -th number in the $i$ -th line represents the number $A_{i,j}(1 \le A_{i,j} \le 10^9)$ --- the number of patients in the block of the $i$ -th row and $j$ -th column in the Matrix city.

$n$ $n$ $j$ $i$ $A_{i,j}(1 \le A_{i,j} \le 10^9)$ $i$ $j$

输出描述:

A integer represents the minimum possible maximum number of workers required to be sent to one block.

示例1

输入

复制

2
1 3
3 2

输出

复制

说明

The new matrix is:

so the answer is 2.