Minimum Effort Path

You are given a grid with n rows and m columns representing the terrain, where each cell contains an integer height. Your task is to find a path from the top‐left corner (0, 0) to the bottom‐right corner (n-1, m-1) such that the effort of the path is minimized.

The effort of a path is defined as the maximum absolute difference in heights between any two consecutive cells along the path. In other words, if the path consists of cells with heights \(h_0, h_1, \dots, h_k\), then its effort is given by:

[ \text{effort} = \max_{1 \le i \le k} \left|h_i - h_{i-1}\right| ]

Your goal is to compute the minimum possible effort required to travel from the starting cell to the destination cell.

inputFormat

Input is given from standard input (stdin). The first line contains two integers n and m, representing the number of rows and columns respectively. This is followed by n lines, each containing m integers that represent the heights of the cells in the grid.

outputFormat

Print a single integer to standard output (stdout): the minimum effort required to travel from the top-left corner to the bottom-right corner of the grid.## sample

3 3
1 2 2
3 8 2
5 3 5

2