The Grasshopper and the Ant#5528
The intricate relationship between the grasshopper and the ant is not only captured in Krylov's famous fable. In a Georgian folk tale, the grasshopper saves the ant from drowning in a river before the ant learns to swim. The current status of the ant's swimming skills remains untold in the folk epic. The tale of how the grasshopper rescued the ant is a story for another time. Here, we pick up the narrative when the grateful ant decides to invite the grasshopper to the finest khinkali restaurant in their forest home. At this moment, the friends are at the forest's edge, represented as a rectangular grid of size M \times N. Each cell in this grid has a specific height above sea level. The friends start at cell , and the restaurant is located at the opposite corner in cell (M, N). With each move, they can step into any adjacent cell within the forest. Two cells are considered adjacent if they share a side.
The challenge is to choose a path that minimizes their fatigue. However, the grasshopper prefers a path with fewer cells, while the ant favors a path with the lowest maximum height to climb. The starting and ending cells are part of the path. Both friends, being courteous as per the tale, insist on choosing the path that benefits the other more. Since it is unclear who will be more persuasive, we must be prepared to assist them in both scenarios. Therefore, we need to determine the path length, which is the number of cells traversed (including the start and end), and the maximum height encountered on the path, under the following conditions:
The route most convenient for the grasshopper is chosen, and if there are several such routes, the one that best suits the ant's preferences is selected among them.
The route most convenient for the ant is chosen, and if there are several such routes, the one that best suits the grasshopper's preferences is selected among them.
The first line contains integers and (2 \leq M, N \leq 500).
Each of the next lines contains integers. The -th integer of the (i+1)-th line represents the height of cell . Each height is an integer within the range inclusive.
Output two lines, each containing two integers. The first line should display the length and the maximum height of the path for the first scenario, and the second line should provide the corresponding values for the second scenario.
Example 1