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 of the newly appointed Barons will be allowed to construct a castle in the new territory and to collect taxes from the surrounding lands.

The King has commissioned a map of the new territory, marked off in a grid. Each square on the grid is approximately the distance a man on horseback could ride in one day. Each Baron will choose a square in which to build his castle. As the senior commander, you will choose first.

For the sake of this selection, castles will be presumed to lie at the center of the selected square. The two castles must be built in squares whose centers are more than three days’ ride from one another.

Each Baron will be allowed to collect taxes from the peasants in any square whose center is 6 days’ ride or less from that Baron’s castle and that is closer to that Baron’s castle than to the other Baron’s. Squares that are equidistant from the two castles do not contribute taxes to either castle.

Tensions had been rising between you and your fellow commander throughout the military campaign. You are certain that, eventually, the two of you will be fighting for control of the entire territory. Until then, the collection of taxes is crucial to your military build-up. You must make sure that you collect more tax money than your rival, and that you outstrip him by as much as possible.

Your advisor has studied the records kept by the scribes of the former King of this territory, and so has been able to estimate the tax revenue that can be expected from each square. Based on this, you want to select the site for your own castle that guarantees the best possible advantage taxes no matter what space your rival baron may select.

NOTE: Distances are Euclidean (distance between the center of two squares as the crow flies).

The first line of input will contain two integers, w, and h, denoting the width and height (in numbers of squares) of the map. w and h will be in the range 1–50, inclusive.

This is followed by w × h integers distributed across an arbitrary number of subsequent lines. Each of these represents the expected tax collection (in gold pieces per year) for one map square. They occur in the order:

(0, 0)(1, 0), . . . , (w − 1, 0)(0, 1)(1, 1), . . . , (w − 1, h − 1)

Each item will be in the range 0–40, inclusive. A value of 0 denotes water or land that is otherwise uninhabitable—castles cannot be built on those squares.

All maps used as input in this problem will be large enough to guarantee that both castles can be placed on a non-zero square, no matter where the first one is placed (i.e., you cannot crowd your rival entirely off the map).

Output from this program consists of a single line of the form:

Place your castle at: X Y

where X and Y are two integers, separated by a single space, denoting the optimal placement of your castle, indexed from 0.

If there is more than one location on the map that may be chosen to achieve the same maximal advantage over your rival, any one of those positions will be an acceptable answer.