Problem Description

There is a grid of $ N $ rows and $ M $ columns, where each cell contains one of the characters S, G, or a digit from 1 to 9. There is exactly one cell with S and exactly one cell with G.

The state of the grid is represented by a 2D array $ A $ of size $N \times M$, where the character in the $ i $-th row and $ j $-th column is $ A_{i, j} $.

You are to start from the cell with S and move to the cell with G. From any cell, you can move to one of the four adjacent cells. Moving outside the grid is not allowed.

Find the minimum number of moves required to reach the cell with G from the cell with S through a path that includes cells with digits 1, 2, ..., 9 in this order. If no such path exists, output $ -1 $.

A path includes cells with digits 1, 2, ..., 9 in order if, for $ k $ moves with characters $ c_0 = $ S, $c_1, c_2, \cdots, c_k =$ G, there exist $1 \leq i_1 \leq i_2 \cdots \leq i_9 < k$ such that $ c_{i_1} = $ 1, $ c_{i_2} = $ 2, ..., $ c_{i_9} = $ 9.

Note that the same cell can be visited multiple times, and passing through cells with S or G is allowed.

Input Format

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

$ N $ $ M $ $A_{1,1}A_{1,2}\cdots A_{1,M}$ $A_{2,1}A_{2,2}\cdots A_{2,M}$ $ : $ $A_{N,1}A_{N,2}\cdots A_{N,M}$

Output Format

Output the minimum number of moves in a path that includes cells with digits 1, 2, ..., 9 in this order. If no such path exists, output $ -1 $.

Sample Input and Output

Sample Input #1

3 4
1S23
4567
89G1

Sample Output #1

17

Sample Input #2

1 11
S134258976G

Sample Output #2

20

Sample Input #3

3 3
S12
4G7
593

Sample Output #3

-1

Notes/Hints

Note

Discussion of this problem is prohibited until May 2, 2020, 18:00 JST. Disclosure of information about which problems were solved may result in claims for compensation.

After the contest, it is acceptable to publish total scores and certification levels, but please refrain from disseminating information about which specific problems were solved.

Constraints

• $1 \leq N, M \leq 50$
• $ A $ consists of S, G, and digits from 1 to 9
• There is exactly one cell with S and exactly one cell with G

Sample Explanation 1

There are two cells with 1. Representing the cell at the $ i $-th row and $ j $-th column as $ (i, j) $, the following path has 17 moves, which is the minimum: - (1, 2), (1, 1), (1, 2), (1, 3), (1, 4), (1, 3), (1, 2), (1, 1), (2, 1), (2, 2), (2, 3), (2, 4), (2, 3), (2, 2), (2, 1), (3, 1), (3, 2), (3, 3) For example, the bold cells contain 1, 2, ..., 9 in this order.

Sample Explanation 3

Since 6 is not included, there is no path that satisfies the condition. Output $ -1 $.

见题面 Input 部分

见题面 Output 部分