N번째 큰 수

크기가 N × N인 표에 서로 다른 정수 N^2개가 들어 있다. 각 수는 바로 위 칸에 있는 수보다 크다. 즉, 같은 열에서는 아래로 내려갈수록 수가 커진다.

아래는 N = 5인 표의 한 모습이다.

이와 같은 표가 주어질 때, 전체 N^2개의 수 중에서 N번째로 큰 수를 구하라.

첫째 줄에 N (1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 정수가 주어진다. 표에 적힌 수는 모두 -10^9 이상 10^9 이하의 정수이다.

첫째 줄에 N번째로 큰 수를 출력한다.