Tractor

One of Farmer John's fields is especially hilly, and he wants to buy a new tractor to drive around on it. The field is given as an $N \times N$ grid of non-negative integer elevations ($1 \le N \le 500$); the value in each cell is that cell's elevation.

A tractor may move only one step at a time, to a cell adjacent to the north, east, south, or west. If you buy a tractor of cost $c$, it can move freely between any two adjacent cells whose elevation difference is at most $c$ (a step across an elevation difference greater than $c$ is impossible).

Farmer John wants to be able to start from some cell and visit at least half of all the cells in the field (rounded up if the number of cells is odd). Compute the minimum cost of a tractor that makes this possible.

• Line 1: the integer $N$.
• Lines 2 to $N+1$: each line contains $N$ space-separated non-negative integers describing one row of the field. Each elevation is at most 1,000,000.

• Print a single line with the minimum cost of a tractor able to drive around at least half of the field.

In the example input the field is a $5 \times 5$ grid, so the tractor must visit at least 13 of the 25 cells. A tractor of cost 3 can move between elevation 0 and elevation 3, so it can reach the region of cells at elevation 0 together with the region of cells at elevation 3. Together these make up at least half of the field, so the answer is 3.