Problem Description

We have rejudged the problem. After finishing her break, Joisino decided to explore a dungeon with a fellow adventurer she had just met. The journey was going smoothly, but they encountered an accident and had to rush to a safe zone.

The dungeon consists of $ R $ rooms in the north-south direction and $ C $ rooms in the east-west direction, forming a grid of $ R*C $ rooms on each level. Joisino and her companion are currently in the northwest room of the current level. The safe zone is located in the southeast room of the level reached after descending $ N-1 $ times.

Each level, except for the one containing the safe zone, has several holes. Falling into a hole allows one to descend to the next level. If a hole is located $ x $ rooms east and $ y $ rooms south from the northwest room, the room it leads to is also $ x $ rooms east and $ y $ rooms south from the northwest room of the next level. Note that the room one falls into does not have a hole. Also, one must fall into a hole when entering a room with one.

Each room has a danger level, which indicates the risk of passing through that room. The danger level of a room with a hole is $ 0 $, but the danger level of the room one falls into is considered. The danger levels of the room Joisino is currently in and the safe zone room are both $ 0 $.

Joisino wants to move to the safe zone while avoiding as much danger as possible. Therefore, she decided to take the route with the minimum total danger level among the shortest paths (routes that do not move west or north). Being an excellent programmer, Joisino decided to write a program to calculate the minimum total danger level for such a route.

Input Format

The input is given from the standard input in the following format:

$ N $ $ R $ $ C $ $ S_1 $ $ S_2 $ : $ S_{N*R} $

• The first line contains the number of levels $ N(2≦N≦100) $ and the size of each level $ R(2≦R≦100) $ and $ C(2≦C≦100) $, separated by spaces.
• The next $ N*R $ lines contain information about each level. From line $ K*R+1 $ to $ K*R+R $ for each $ K(0≦K≦N-1) $, there are $ R $ lines describing the level reached after descending $ K $ times. Each of these $ R $ lines contains a string of length $ C $. This string consists of characters H and digits from 0 to 9. If the j-th character is H, it indicates that there is a hole $ j-1 $ rooms east and $ i-1 $ rooms south from the northwest room. If the j-th character is 0, it indicates that the room is either the start or goal. If the j-th character is a digit from 1 to 9, it indicates the danger level of the room $ j-1 $ rooms east and $ i-1 $ rooms south from the northwest room.
• For all inputs, it is guaranteed that there is at least one route to reach the safe zone.

Output Format

Output the minimum total danger level in one line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

3 3 3
06H
H14
257
337
15H
2H8
829
653
470

Sample Output #1

9

Sample Input #2

2 5 3
013
871
7HH
163
92H
959
248
792
447
550

Sample Output #2

14

Notes/Hints

Scoring

There are no partial points for this problem. Correctly solving it will award $ 60 $ points.

Sample Explanation 1

• Moving south → falling into a hole → east → east → falling into a hole → south minimizes the total danger level.

见题面 Input 部分

见题面 Output 部分