21041번 - Largest Exotic Number 출처다국어분류

• 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, A_a,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): A_i,j (1 ≤ A_i,j ≤ 100,000) denoting the matrix element at i-th row and j-th column for 1 ≤ i ≤ N and 1 ≤ j ≤ N, respectively.

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