Today is Penguin07's birthday, and he decided to build a pathway from National Tsing Hua University (NTHU) to his home as a birthday gift.
We can think of Hsinchu as an N×N grid, where NTHU is located at the coordinate (1, 1) and Penguin07's home is at (N, N). The value hi,j represents the elevation at the grid cell with coordinates (i, j).
Penguin07's construction team needs to build a pathway from NTHU (1,1) to Penguin07's home (N,N). The pathway can be seen as a route within this grid, moving in any of the four cardinal directions (up, down, left, right) from (1, 1) to (N, N).
Considering Penguin07's safety while walking on the pathway, attention must be paid to the elevation differences between consecutive steps. The goal is to establish a pathway with the minimum possible maximum elevation difference. Additionally, under the condition of this minimum maximum elevation difference, the shortest possible path length should be considered.
Please output the minimum value of the maximum elevation difference for such a pathway and, given this minimum elevation difference, the shortest path length.
The first line contains a number n (1 ≤ n ≤ 300), representing the size of the region.
The following n lines each contain n positive integers. Each integer hi, j (1 ≤ hi, j ≤ 106) represents the elevation at position (i, j).
Output two lines: the first line should output the minimum value of the maximum elevation difference in the chosen pathway, and the second line should output the length of the shortest path from the top-left to the bottom-right under this maximum elevation difference.