Leveling the Tiles

Mirko owns an uneven plot of land that measures $R \times S$ meters and is paved with $R \times S$ tiles of size $1 \times 1$ meter. The ground is uneven, so every tile has its own height, given in centimeters.

Two tiles are adjacent if they share a side. A tile has at most four adjacent tiles. Two tiles are connected if you can walk from the first to the second, moving in each step from the current tile to an adjacent tile of the same height.

A storm starts dropping large chunks of ice on the land. When a chunk lands on a tile, the impact pushes that tile down by 1 centimeter, and every tile connected to it goes down by 1 centimeter as well.

Compute the smallest number of ice chunks that can fall so that all tiles end up at the same height. Each chunk falls at a different moment and lands on exactly one tile.

The first line contains two natural numbers $R$ and $S$, the dimensions of the land. ($2 \le R, S \le 1000$)

Each of the next $R$ lines contains $S$ natural numbers, the heights of the corresponding tiles in centimeters. Every height is between $1$ and $10^9$.

Print the minimum number of ice impacts after which all tiles have the same height.

In the first example, after one chunk lands on the middle tile, every tile except the last one has height 2. After one more chunk lands on the middle tile, all tiles have height 1.