트랙터

농부 John의 밭 하나는 유난히 언덕이 많아서, 그는 그 위를 돌아다닐 새 트랙터를 사려고 한다. 이 밭은 음이 아닌 정수 고도들로 이루어진 $N \times N$ 격자로 주어진다 ($1 \le N \le 500$). 각 칸의 값은 그 칸의 고도이다.

트랙터는 상하좌우로 인접한 칸으로만 한 번에 한 칸씩 이동할 수 있다. 비용이 $c$인 트랙터를 사면, 고도 차이가 $c$ 이하인 인접한 두 칸 사이를 자유롭게 오갈 수 있다(고도 차이가 $c$를 초과하는 이동은 불가능하다).

John은 어떤 한 칸에서 출발하여 밭 전체 칸의 절반 이상을 방문할 수 있기를 원한다(전체 칸 수가 홀수이면 올림한 값 이상). 이를 만족하는 트랙터를 사기 위한 최소 비용을 구하여라.

• 첫째 줄: 정수 $N$.
• 둘째 줄부터 $N$개의 줄: 각 줄에는 공백으로 구분된 $N$개의 음이 아닌 정수가 주어지며, 밭의 한 행을 나타낸다. 각 고도는 최대 1,000,000이다.

• 한 줄에, 밭의 절반 이상을 돌아다닐 수 있는 트랙터의 최소 비용을 출력한다.

예시 입력에서 밭은 $5 \times 5$ 격자이므로, 트랙터는 25칸 중 13칸 이상을 방문해야 한다. 비용이 3인 트랙터는 고도 0과 고도 3 사이를 오갈 수 있으므로, 고도가 0인 칸들의 구역과 고도가 3인 칸들의 구역을 모두 방문할 수 있다. 이 두 구역을 합하면 밭의 절반 이상이 되므로 답은 3이다.