The Grasshopper and the Ant
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×N. Each cell in this grid has a specific height above sea level. The friends start at cell (1, 1), 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's 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 multiple routes exist, the one that best suits the ant's preferences is selected.
The route most convenient for the ant is chosen, and if multiple routes exist, the one that best suits the grasshopper's preferences is selected.
Input
The first line contains the integers M and N, where 2 ≤ M, N ≤ 500.
Each of the next M lines contains N integers. The j-th integer of the i+1-th line represents the height of cell (i, j). Each height is an integer within the range 1..1000000000 inclusive.
Output
Output two lines, each containing two integers. The first line should display the length and maximum height of the path for the first scenario, and the second line should provide the corresponding values for the second scenario.