A hiker crosses an R-by-C grid of integer elevations, stepping one cell at a time up, down, left, or right, from the top-left cell (0,0) to the bottom-right cell (R-1,C-1).
The strain of a route is the maximum, over all consecutive steps on the route, of the absolute difference in elevation between the two cells of that step. The hiker wants a route of minimum possible strain.
Report that minimum strain. (A single-cell grid has strain 0.)
Input format
Line 1: two integers R and C.
Next R lines: each contains C space-separated integers, the elevations.
Output format
A single integer: the minimum possible strain over all routes from start to end.
Constraints
- 1 <= R, C <= 200
- 0 <= each elevation <= 1000000