시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 38 20 14 50.000%

문제

  • Athanasios: I have an interesting problem to be proposed for ACM-ICPC INC 2017!
  • Berdine: What the problem is about?
  • Athanasios: It involves an exotic algorithm.
  • Berdine: ... alright, let's hear it!

For readability reason, the element of a matrix A at the a-th row and b-th column, Aa,b, will be written as (a, b). The matrix indices start at 1.

Given a matrix A of size N × N, two elements in the matrix (a, b) and (c, d) are called an exotic pair if all these three conditions are satisfied:

  1. (a, b) and (c, d) have the same value.
  2. At least one of the following condition is satisfied: a ≠ c, or b ≠ d.
  3. Both of the following conditions are satisfied: a ≤ c, and b ≤ d.

For example, given a matrix:

3 2 1
5 2 3
4 3 4

There are four exotic pairs in the matrix:

  • (1, 1) and (2, 3), of value 3;
  • (1, 1) and (3, 2), of value 3;
  • (2, 1) and (2, 2), of value 2;
  • (3, 1) and (3, 3), of value 4.

Among those four exotic pairs, (3, 1) and (3, 3) have the largest value (of 4); we call this kind of number as the largest exotic number.

Your task in this problem is to find the largest exotic number given a matrix, or output -1 if there is no such number.

입력

The first line contains an integer: N (2 ≤ N ≤ 300) denoting the size of the matrix. The following N lines, each contains N integers (each separated by a single space): Ai,j (1 ≤ Ai,j ≤ 100,000) denoting the matrix element at i-th row and j-th column for 1 ≤ iN and 1 ≤ jN, respectively.

출력

The output contains the largest exotic number for the given input, in a line. Output -1 if there is no such number.

예제 입력 1

3
3 2 1
5 2 3
4 3 4

예제 출력 1

4

예제 입력 2

4
3 2 1 4
4 2 1 4
5 1 2 1
3 1 5 6

예제 출력 2

5

예제 입력 3

2
1 2
2 4

예제 출력 3

-1