N 君は毎日学校に通っているが，その道のりはとても長い．さらに今は暑い夏である．道中，蝉が五月蝿い．出来れば避けたいものである．ところで情報化が発達した現代社会においては，家に居ながらにしてどこに何匹の蝉がいるか調べることが出来る．その情報を使い，途中で出会う蝉の数が最も少ない道で学校に行くことに決めた．
家と学校が描かれた地図は長方形状になっており，H × W 個のブロックに分割される．一番左上のブロックに N 君の家があり，一番右下に学校がある．彼は学校へまっすぐ登校したいので家の方に逆戻りすることはない (地図において，右か下のブロックにしか移動しない)．各ブロックにおいて，そこにいる蝉の数だけ不快になる．どのような道を選べば，不快な度合いを最小化，つまり出会う蝉の数を最小に出来るだろうか．
最初の行には二つの数字 H，W がこの順で与えられる．H は地図の縦方向のブロック数を示し，W は横方向のブロック数を示す．
次の H 行に蝉の情報が書かれた地図が与えられる．各行は W 文字からなり，各文字は対応するブロック中の蝉の数を示す．ブロック中の蝉の数は 9 を超えることはない．
出会う蝉の数の最小値を 1 行で与えよ．
3 3 023 321 120
5
5 6 000000 923450 000000 054329 000000
4
N 君は右か下のブロックにしか移動しないことに注意せよ．
6 9 089712364 781263576 937526351 736589623 217835653 837479570
46