Minimize Maximum Difference on Path

You are given an N×M grid of integers where each cell represents a height. Your task is to find a path from the top-left corner (cell (0, 0)) to the bottom-right corner (cell (N-1, M-1)) such that the maximum absolute difference between the heights of adjacent cells along the path is minimized.

You can move up, down, left, or right. Formally, if you travel along a path P = [p₀, p₁, ..., p_k] where each p_i is a cell, define the cost of the path as:

[ cost(P) = \max_{0 \le i < k} ; |height(p_{i+1}) - height(p_i)| ]

Your goal is to determine the minimum possible cost(P) among all valid paths from (0, 0) to (N-1, M-1).

Note: It is guaranteed that there is at least one valid path, and the grid dimensions satisfy N, M \ge 1.

inputFormat

The first line contains two integers N and M — the number of rows and columns respectively.

The following N lines each contain M integers representing the heights of the grid cells.

Input is read from standard input.

outputFormat

Output a single integer — the minimized maximum absolute difference along a valid path from the top-left corner to the bottom-right corner. Output is written to standard output.

## sample

3 3
1 2 2
3 8 2
5 3 5

2