Millionaire Madness

A friend of yours, a duck who is deep in debt, has asked for help with a job that would clear what he owes. His uncle is an extremely rich duck whose vault is filled with mountains of coins. One coin in that vault matters to the uncle far more than the rest, and it normally sits on a velvet cushion under a glass dome.

During a recent rearrangement of the vault the special coin was moved into the piles by mistake. It has now been located, but it lies in the corner opposite the entrance, and the mountains of coins make reaching it hard.

The uncle will pay your friend to bring the coin back, on the condition that your friend brings his own climbing gear. Your friend plans to buy a ladder. A longer ladder lets him scale higher cliffs but also costs more, so he wants the shortest ladder that still lets him reach the coin.

The vault is a rectangular grid of coin stacks whose heights are given in meters. The entrance is at the north west corner and he starts at the height of that stack. The special coin is at the south east corner. From one stack he moves to the stack immediately north, west, south or east. He cannot jump or fly, so climbing $n$ meters up requires a ladder of at least $n$ meters. Dropping down is free no matter how large the difference is, because gravity does the work.

Find the length of the shortest ladder that lets him get from the north west corner to the south east corner.

The first line contains two integers $M$ and $N$, the length and the width of the vault ($1 \le M, N \le 1000$).

Each of the next $M$ lines contains $N$ integers. The $j$-th integer on the $i$-th of those lines is the height of the coin stack in row $i$, column $j$. The first of those lines describes the north most stacks from west to east and the last one describes the south most stacks from west to east. Every height $h$ satisfies $0 \le h \le 10^9$.

Print one integer, the length in meters of the shortest ladder that allows a walk from the north west corner to the south east corner.