AT_tkppc2015_d サポーター (Supporter)

[problemUrl]: https://atcoder.jp/contests/tkppc/tasks/tkppc2015_d **リジャッジをしました。** 休憩を終えたjoisinoお姉ちゃんは、偶然知り合った冒険者の人とともに、ダンジョンに潜ることにした。 順調な道のりだったが、途中で事故が起き、急いで安全地帯まで向かう必要に迫られた。 このダンジョンは、全ての階層で、南北に$ R $個、東西に$ C $個、全部で$ R*C $個の部屋が格子状に並んでいる。 joisinoお姉ちゃんたちは現在いる階層の、最も北西の部屋にいる。 安全地帯は、現在の階層から$ N-1 $回降りた階層の、最も南東の部屋である。 安全地帯の存在する階層以外の各階層にはいくつか穴が存在する。 穴は部屋の中にあり、穴に落ちることで、一つ下の階層に降りることができる。 この時、穴のあった場所が、北西の部屋から、東に$ x $ 南に$ y $ 進んだ部屋だった場合、落ちた先の部屋も、北西の部屋から東に$ x $ 南に$ y $ 進んだ部屋である。 なお、落ちた先の部屋にも穴があるということはない。 また、穴のある部屋に入ったときは、必ず落ちなくてはならない。 それぞれの部屋には、危険度というものがある。 この危険度が高ければ高いほど、その部屋を通る危険が大きいことを表す。 穴のある部屋の危険度は$ 0 $であるが、落ちたあとの部屋の危険度は考慮するものとする。 なお、現在joisinoお姉ちゃんがいる部屋、安全地帯の部屋の危険度は$ 0 $である。 joisinoお姉ちゃんたちは、できるだけ危険を避けつつ、安全地帯まで移動したい。 そのために、最短経路(西や北に移動しないようにした道順)の中で、通る部屋の危険度の合計が最小となるルートで進むことにした。 優秀なプログラマーであるjoisinoお姉ちゃんは、そのようなルートで進んだ時の、危険度の合計を求めるプログラムを作成することにした。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ R $ $ C $ $ S_1 $ $ S_2 $ : $ S_{N*R} $ - $ 1 $行目には、通る階層の数$ N(2≦N≦100) $と、階層の大きさを示す整数$ R(2≦R≦100) $と$ C(2≦C≦100) $が、空白区切りで書かれている。 - $ 2 $行目からの$ N*R $行のうち、$ K*R+1 $行目からの$ R $行には、現在の階層から$ K(0≦K≦N-1) $回降りた階層の情報が書かれている。 この$ R $行のうち$ i $行目には、長さ$ C $の文字列が書かれている。 この文字列は、`H`と、`0`から`9`までの文字で構成されている。 j番目の文字が`H`である場合、それは、北西の部屋から東に$ j-1 $ 南に$ i-1 $進んだ部屋に穴があることを示す。 j番目の文字が`0`である場合、それは、北西の部屋から東に$ j-1 $ 南に$ i-1 $進んだ部屋がスタート地点もしくはゴール地点であることを示す。 j番目の文字が`1`から`9`の間の数字であった場合、それは、北西の部屋から東に$ j-1 $ 南に$ i-1 $進んだ部屋の危険度がその数字であることを示す。 - 全ての入力において、安全地帯へ到達するルートが一つ以上あることが保障されている。

危険度の合計の最小値を一行で出力せよ。 また、出力の末尾には改行を入れること。

### 配点 この問題に部分点はない。正解すると$ 60 $点が得られる。 ### Sample Explanation 1 \- 南→穴に落ちる→東→東→穴に落ちる→南 と移動することで、危険度の合計を最小化できる。