問題 B 蝉

問題文

N 君は毎日学校に通っているが，その道のりはとても長い．さらに今は暑い夏である．道中，蝉が五月蝿い．出来れば避けたいものである．ところで情報化が発達した現代社会においては，家に居ながらにしてどこに何匹の蝉がいるか調べることが出来る．その情報を使い，途中で出会う蝉の数が最も少ない道で学校に行くことに決めた．

家と学校が描かれた地図は長方形状になっており，H × W 個のブロックに分割される．一番左上のブロックに N 君の家があり，一番右下に学校がある．彼は学校へまっすぐ登校したいので家の方に逆戻りすることはない (地図において，右か下のブロックにしか移動しない)．各ブロックにおいて，そこにいる蝉の数だけ不快になる．どのような道を選べば，不快な度合いを最小化，つまり出会う蝉の数を最小に出来るだろうか．

入力形式

最初の行には二つの数字 H，W がこの順で与えられる．H は地図の縦方向のブロック数を示し，W は横方向のブロック数を示す．
次の H 行に蝉の情報が書かれた地図が与えられる．各行は W 文字からなり，各文字は対応するブロック中の蝉の数を示す．ブロック中の蝉の数は 9 を超えることはない．

出力形式

出会う蝉の数の最小値を 1 行で与えよ．

制約

• 2 ≤ H ≤ 50
• 2 ≤ W ≤ 50
• N 君の家と学校には蝉はいない．
• ブロック中の蝉の数は 0 以上 9 以下である．

入出力例

入力例 1

3 3
023
321
120

出力例 1

5

入力例 2

5 6
000000
923450
000000
054329
000000

出力例 2

4

N 君は右か下のブロックにしか移動しないことに注意せよ．

入力例 3

6 9
089712364
781263576
937526351
736589623
217835653
837479570

出力例 3

46

---