가장 큰 엑조틱 수

면접 대비

시간 제한1초메모리 제한512 MB

요약

N×N 행렬에서 한 셀이 다른 셀의 왼쪽 위에 있으면서 두 셀의 값이 같은 경우를 찾고, 그런 값 중 가장 큰 값을 출력하며 없으면 -1을 출력한다.

난이도: 보통10점 중 5점
유형: 정렬, 행렬, 그리디, 배열
정답자: 아직 제출이 없습니다

문제

Athanasios: ACM-ICPC INC 2017에 낼 흥미로운 문제가 하나 있어!
Berdine: 무슨 문제인데?
Athanasios: 엑조틱 알고리즘이 들어가 있어.
Berdine: ... 좋아, 한번 들어보자!

읽기 쉽도록 행렬 A의 a번째 행, b번째 열의 원소 A**a,b는 (a, b)로 쓴다. 행렬의 인덱스는 1부터 시작한다.

크기가 N × N인 행렬 A가 주어질 때, 행렬의 두 원소 (a, b)와 (c, d)가 다음 세 조건을 모두 만족하면 엑조틱 쌍이라고 한다.

(a, b)와 (c, d)의 값이 같다.
다음 중 적어도 하나를 만족한다: a ≠ c 또는 b ≠ d.
다음 두 조건을 모두 만족한다: a ≤ c이고 b ≤ d.

예를 들어 행렬이 다음과 같다고 하자.

3 2 1
5 2 3
4 3 4

이 행렬에는 네 개의 엑조틱 쌍이 있다.

(1, 1)과 (2, 3), 값은 3
(1, 1)과 (3, 2), 값은 3
(2, 1)과 (2, 2), 값은 2
(3, 1)과 (3, 3), 값은 4

이 네 엑조틱 쌍 중에서 (3, 1)과 (3, 3)의 값이 4로 가장 크다. 이런 수를 가장 큰 엑조틱 수라고 한다.

이 문제에서 할 일은 행렬이 주어졌을 때 가장 큰 엑조틱 수를 구하는 것이다. 그런 수가 없으면 -1을 출력한다.

입력

첫째 줄에는 행렬의 크기를 나타내는 정수 N (2 ≤ N ≤ 300)이 주어진다. 다음 N개 줄에는 각각 N개의 정수가 하나의 공백으로 구분되어 주어진다. A**i,j (1 ≤ A**i,j ≤ 100,000)는 1 ≤ i ≤ N, 1 ≤ j ≤ N인 i번째 행, j번째 열의 행렬 원소이다.

출력

주어진 입력에 대한 가장 큰 엑조틱 수를 한 줄에 출력한다. 그런 수가 없으면 -1을 출력한다.

예제3

예제 1
입력
```
3
3 2 1
5 2 3
4 3 4
```
예상 출력
```
4
```
예제 2
입력
```
4
3 2 1 4
4 2 1 4
5 1 2 1
3 1 5 6
```
예상 출력
```
5
```
예제 3
입력
```
2
1 2
2 4
```
예상 출력
```
-1
```