북극에서 동굴을 탐험 중이던 당신과 당신의 팀은 고대 유적이 얼어붙은 얼음 위에서 발견한 보물 지도를 손에 넣었다.

이 지도는 N×N 크기의 얼음길을 나타내며, 각 칸에는 보물의 가치가 적혀 있다.

특이하게도 이 지도는 한 가지 규칙을 가진다

모든 숫자는 자신의 왼쪽 칸보다 크다. (즉, 맨 첫 번째 열을 제외하고 모든 칸 (i, j)의 값은 (i, j-1)보다 크다.)

당신의 팀은 총 N명으로 구성되어 있다. 각자 N개의 보물을 차례로 가져가기로 했고, 보물 분배는 아래와 같은 방식으로 진행되었다:

보물은 가치가 큰 순서대로 하나씩 분배된다.

나이가 가장 많은 사람이 가장 비싼 보물을 가져가고,

그다음 사람이 두 번째로 비싼 보물을,

…

N번째로 나이가 많은 사람이 마지막으로 선택한다.

위 과정을 N번 반복하여, 각 사람은 총 N개의 보물을 가지게 되었다.

그럼 N번째로 나이가 많은 사람이 가진 보물 중에 가장 비싼 보물의 가치는 얼마일까?

입력 설명

첫째 줄에 정수 N (1 <= N <= 1,500)이 주어진다.

둘째 줄부터 N개의 줄에 걸쳐, N개의 정수가 주어진다.

이 값들은 지도에 적힌 보물의 가치를 나타낸다. (가치는 음수 일 수 있습니다.)

(각 값은 -1,000,000,000 이상 1,000,000,000 이하의 정수이며, 중복되지 않는다.)

출력 설명

이 지도에서 N번째로 큰 보물의 가치를 출력하라.

예제 입력

5
12 13 21 48 52
7  8 10 14 20
9 11 26 28 32
15 19 31 35 41
5  6 16 25 49

예제 출력

35

힌트

반복문 사용시 시간이 부족할 수 있습니다. 우선순위 큐를 최대한 활용해보세요.

언어별 리소스 제한