Problem Description

Indeed Corporation's office is constructed by combining regular hexagons.
As a new recruit, A-kun is skilled in sports and can jump over the partitions between the hexagons.
Currently, A-kun needs to rush from location $ s $ to location $ t $.
However, when entering a hexagon space, he is asked "How are you?" by the people there, which takes time.
Moreover, if there are $ n $ people in one hexagon space, A-kun will be asked "How are you?" $ n $ times.
What is the minimum number of times A-kun will be asked "How are you?" when moving from $ s $ to $ t $?
Note that at locations $ s $ and $ t $, A-kun will not be asked "How are you?".

Input Format

The input is given in the following format:

$ R $ $ C $ $ a_{11} $ $ a_{12} $ $ ... $ $ a_{1C} $ $ a_{21} $ $ a_{22} $ $ ... $ $ a_{2C} $ $ ... $ $ a_{R1} $ $ a_{R2} $ $ ... $ $ a_{RC} $

• The first line contains the number of rows $ R $ and columns $ C $ of hexagon spaces in the office ($1\ \leq\ R,C\ \leq\ 100$, $R\ \times\ C\ \geq\ 2$).
• The next $ R $ lines contain the number of people $ a_{ij} $ in each hexagon.
• $ a_{ij} $ consists of s, t, 0 to 9.
• Exactly one of $ a_{ij} $ is s and exactly one is t, guaranteed.
• Refer to the diagram below for the correspondence between $ a_{ij} $ and the actual values.

Output Format

Output the desired value in one line.

Sample Input and Output

Sample Input #1

3 4
s120
0321
220t

Sample Output #1

2

Sample Input #2

5 5
s0010
12032
11303
12114
5001t

Sample Output #2

1

Notes/Hints

Sample Explanation 1

见题面 Input 部分

见题面 Output 部分