Minimum Effort Path

You are given a 2D grid \(H\) of size \(m \times n\) where \(H[i][j]\) represents the height at cell \((i, j)\). From any cell, you can move up, down, left, or right. The effort of a path is defined as the maximum absolute difference between the heights of consecutive cells on that path.

Formally, let a path be a sequence of cells \((i_0,j_0), (i_1,j_1), \dots, (i_k,j_k)\) where \((i_0,j_0) = (0,0)\) and \((i_k,j_k) = (m-1,n-1)\). The effort of this path is \[ \max_{1 \leq t \leq k} \left|H[i_t][j_t] - H[i_{t-1}][j_{t-1}]\right| \] Your task is to find such a path with the minimum possible effort.

inputFormat

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

Each of the following \(m\) lines contains \(n\) integers separated by spaces, representing the heights in the grid.

outputFormat

Output a single integer representing the minimum effort required to travel from the top-left corner to the bottom-right corner of the grid.

3 3
1 2 2
3 8 2
5 3 5

2