A quarry is surveyed as a grid of R rows and C columns of integer elevations. A hauler starts at the top-left cell (0,0) and must reach the bottom-right cell (R-1, C-1), moving only up, down, left, or right to an adjacent cell.
The strain of a route is the maximum, over all consecutive steps of the route, of the absolute difference in elevation between the two cells of that step. Among all routes, find the minimum possible strain. (A route that never moves — when the grid is a single cell — has strain 0.)
Input format
Line 1: two integers R and C.
Each of the next R lines: C space-separated integers, the elevations of that row.
Output format
A single integer: the minimum possible strain of a route from the top-left to the bottom-right cell.
Constraints
- 1 <= R, C <= 100
- 0 <= elevation <= 1000000