cho.shTime limit
1s
Memory limit
12 MB
An N × N table is filled with N^2 distinct integers. Each number is greater than the number directly above it, so every column increases from top to bottom.
The following table shows one possible table when N = 5.
| 12 | 7 | 9 | 15 | 5 |
| 13 | 8 | 11 | 19 | 6 |
| 21 | 10 | 26 | 31 | 16 |
| 48 | 14 | 28 | 35 | 25 |
| 52 | 20 | 32 | 41 | 49 |
Given such a table, find the Nth largest number among all N^2 numbers.
The first line contains N (1 ≤ N ≤ 1,500). Each of the next N lines contains N integers. Every number written in the table is an integer between -10^9 and 10^9, inclusive.
Print the Nth largest number on the first line.