UChicago Qualifier 2019

Start

2019-05-25 18:30 CEST

UChicago Qualifier 2019

End

2019-05-25 23:30 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -320 days 19:25:07

5:00:00

0:00:00

Problem FGrid Game

Given a $N \times N$ grid of integers, we can choose a combination of $N$ numbers where no two in the same row and no two in the same column. We aim to find a combination of $N$ numbers whose minimum is maximized.

Input

The first line of input consists of an integer $N$, where $1 \leq N \leq 30$. The next $N$ lines each contains $N$ integers, representing the grid. Each integer is in the range $[1..10^6]$.

Output

Output a single integer, representing the maximum possible value of the minimum.

Sample Input 1 Sample Output 1
3
3 1 4
1 5 1
2 9 1

2

Sample Input 2 Sample Output 2
5
17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9

21