Minimum Elevation Loss Path in a Grid

You are given a grid of non-negative integers representing the elevation of each cell. Your task is to find a path from the top-left corner to the bottom-right corner by moving only right or down such that the maximum absolute difference between elevations of any two consecutive cells along the path is minimized.

Formally, if the path is represented as a sequence of cells \( (0,0), (i_1,j_1), \ldots, (m-1,n-1) \), you need to minimize the quantity \[ \max_{k} \left| grid[i_k][j_k] - grid[i_{k+1}][j_{k+1}] \right| \] subject to the constraint that you can only move right or down at every step.

Example:

Input:
3 3
1 3 5
2 8 3
4 9 2
Output:
2

</p>

In the example above, one of the optimal paths is: \(1 \to 3 \to 5 \to 3 \to 2\). The maximum difference along this path is \(\max(|1-3|,|3-5|,|5-3|,|3-2|)=2\), which is the minimum possible.

inputFormat

The first line of input contains two integers \(m\) and \(n\) representing the number of rows and columns of the grid, respectively.

Each of the following \(m\) lines contains \(n\) integers separated by spaces, which represent the elevation values of the grid cells.

You must read the input from stdin.

outputFormat

Output a single integer representing the minimized maximum absolute difference in elevation between adjacent cells along the optimal path.

You must write the output to stdout.

## sample

3 3
1 3 5
2 8 3
4 9 2

2