After years of searching you have come across Captain Blackbeard’s old map showing where his longlost treasure is hidden, deep on the ocean floor. The map was once a hypsometric map – that is, it showed the ocean depth for the region around the treasure – but many of the elevation marks have faded away over time and are no longer legible.

Specifically, the map covers a rectangular part of the ocean, subdivided into an (n - 1) \times (m - 1) rectangular grid of unit squares. The map originally showed the ocean depth d(p) for each point p = (x, y) with integer coordinates 1 ≤ x ≤ n and 1 ≤ y ≤ m. There are no islets in the region. In other words, it is known that d(p) ≥ 0 for all points.

Preparing the map must have been quite a struggle for Blackbeard, since there is no unique natural way to interpolate the depths of points with non-integer coordinates. Consider a unit square on the grid, with corners at the grid points A, B, C, and D in clockwise order, and some depth d(p) stored for each p ∈ \{A, B, C, D\}. One natural way is to interpolate the depth in the triangle ABC linearly, and likewise in CDA. Another equally natural way is to interpolate linearly within BCD, and likewise within DAB. Usually, the results of those two interpolations are different. For example, if d(A) = d(B) = d(C) = 0 and d(D) = 1, the first method results in depths across all of ABC being equal to zero (Figure K.1 left), while the second method results in the depths being positive in the whole interior of the square (right).

Figure K.1: Two ways of interpolating depths within a unit square.

However, Blackbeard was as stubborn as he was cruel and would not let such pesky ambiguities stop him. To find the perfect hiding spot for his treasure, he scoured the seven seas for a region of the ocean where the two methods described above yield the same results for each unit square (or maybe he forced some of his pirates to do a bit of terraforming work to achieve this – scholars disagree).

Back in the present, you are preparing an expedition to retrieve the treasure, and would like to figure out at what depth the treasure could be buried. Specifically, given the remaining depth data of the map, you should calculate the smallest possible depth at the treasure location.

#10901 upload 1 done 1 how_to_reg 1

Treasure Map timer 4s memory 2048MB

#10901

Treasure Map 4s 2048MB