A Baron Landscape

After a successful military campaign, the King decided to reward his two most able commanders with a title and a portion of the newly conquered territory. Each newly appointed Baron may build one castle in the new territory and collect taxes from the surrounding land.

The territory is drawn as a grid map. Each square is roughly the distance a rider on horseback can cover in one day. Each Baron chooses one square in which to build his castle. As the senior commander, you choose first.

A castle is considered to sit at the center of its chosen square. The two castles must be built in squares whose centers are more than three days' ride apart.

Each Baron collects taxes from every square whose center is 6 days' ride or less from that Baron's castle and that is strictly closer to that Baron's castle than to the other's. A square that is equidistant from the two castles pays taxes to neither.

Tensions between you and your fellow commander have grown throughout the campaign, and one day you will fight for the whole territory. Until then, collecting taxes is crucial to your build-up: you must collect more than your rival, and by as wide a margin as possible.

Your advisor has studied the former King's records and estimated the yearly tax revenue (in gold pieces) of every square. Your advantage is defined as (the tax you collect) − (the tax your rival collects). You place your castle first at some position $P$; your rival then places his castle — on a non-zero square, with the two castle centers more than three days' ride apart — so as to minimize your advantage. You want to choose $P$ that maximizes this worst-case advantage.

All distances are Euclidean. The distance between the centers of two squares at integer coordinates $(x_1,y_1)$ and $(x_2,y_2)$ is $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$.

The first line contains two integers $w$ and $h$, the width and height of the map in squares ($1 \le w, h \le 50$).

Then $w \times h$ integers follow, spread over any number of lines. Each is the expected yearly tax revenue (in gold pieces) of one square, listed in the order

$$(0,0),\ (1,0),\ \dots,\ (w-1,0),\ (0,1),\ (1,1),\ \dots,\ (w-1,h-1)$$

Each value is between $0$ and $40$ inclusive. A value of $0$ marks water or otherwise uninhabitable land, where a castle cannot be built.

Every map given as input is large enough that both castles can be placed on non-zero squares no matter where the first castle goes (you cannot crowd your rival entirely off the map).

Print a single integer: the maximum advantage — (your yearly tax) − (your rival's yearly tax) — that you can guarantee when you place your castle first and your rival then places his castle, following the rules above, to minimize your advantage. The advantage may be negative.