During the digitization of the Yandal region map it has become known that it represents a connected area in its bitmap pixel form and is wholly contained within a M × N pixel rectangle. Also, it has the following unique feature: each horizontal or vertical line intersects the region by exactly one segment.
The map was approved for use in portable navigation devices. The screen size of a typical navigator device is A×B pixels. In order to display this particular map the plane should be divided into rectangles of A × B pixels each by horizontal and vertical lines passing by pixel boundaries. Then, each such rectangle (called a tile) containing at least one pixel of map’s area is loaded into the device.
Your task is to choose the positioning of these separating lines for a given map to minimize the total number of tiles to be loaded into the device. You are not allowed to rotate the map or the screen.