暑いのは苦手です

※作問初心者なので、細かいミスがあったらごめんなさい。

問題文

$H \times W$ のグリッド状の地獄があります。 この地獄の上から $i$ 行目、左から $j$ 列目を地点 $(i, j)$ と書きます。 地点 $(i, j)$ の温度は $T_{i, j}$ 度です。

現在、雪女のAliceさんは地点 $(1, 1)$ にいます。Aliceさんは暑いところが苦手なので、できるだけ低温な地点のみを上下左右移動で渡ることで、地点 $(H, W)$ に移動したいと考えています。

Aliceさんが地点 $(1, 1)$ から地点 $(H, W)$ へ移動するために通過しなければならない、最も高温な地点の温度の最小値を答えてください。

制約

• $2 \leq H, W \leq 300$
• $-273 \leq T_{i, j} \leq 10^{18}$
• 入力は全て整数である

入力

入力は以下の形式で与えられる。

出力

答えを出力してください。最後に改行してください。

サンプル

入出力例 1

4 5
0 -3 2 -1 4
-1 2 0 1 -3
-2 2 -3 4 -5
-5 0 1 3 0

1

Alice さんは以下の青色の経路で移動することで、$1$ 度以下の地点のみの移動で目的を達成できます。

$0$ 度以下の地点のみの移動では地点 $(H, W)$ に辿り着くことはできません。

入出力例 $2$

3 3
1000000000000000000 -273 -273
-273 -273 -273
-273 -273 -273

1000000000000000000

入出力例 $3$

9 16
-26 -1 22 -82 27 -85 24 33 75 -35 61 60 28 28 64 -45
-33 -69 -68 83 29 -43 -68 -11 -60 -47 29 40 -76 -43 26 -20
-56 10 47 -58 3 6 -85 89 50 -3 -39 -89 36 35 -77 49
68 -25 93 75 -1 -59 58 -21 28 -44 -49 -3 -63 73 -64 -43
-33 91 73 -70 34 35 -100 -22 -48 -96 74 -54 33 75 -97 -33
-43 -58 82 97 34 70 80 -9 95 9 -51 -24 6 -94 58 -91
47 -41 8 -27 -36 -29 -15 -75 37 -11 -74 -93 -40 67 -58 46
-59 33 14 42 -1 87 -32 -30 -22 49 63 -59 -48 7 53 -9
9 41 73 -52 49 -50 -4 -63 58 -23 13 52 85 -46 -28 -64

27