절벽 오르기

17시 정각, 특수요원 잭이 적진에서 탈출을 시작한다. 적진과 가장 가까운 안전지대 사이에는 거의 수직에 가까운 절벽이 놓여 있다. 잭은 절벽을 뒤덮은 블록에 발을 디디며 이 절벽을 올라가야 한다. 일부 블록은 미끄러워서 발을 안전하게 디디는 데 시간이 걸리고, 어떤 블록은 잭의 무게를 견디지 못할 만큼 약해서 밟을 수 없으므로 피해서 지나가야 한다. 절벽을 다 오르는 데 걸리는 최소 시간을 구하는 프로그램을 작성하라.

절벽은 정사각형 블록으로 덮여 있다. 잭은 절벽 아래 지면에서 출발하여, 맨 아래 줄에 있는 'S' 블록 중 하나에 왼발 또는 오른발을 디디면서 오르기를 시작한다. 블록에 적힌 숫자는 그 블록의 "미끄럼 정도"이다. $t$($1 \le t \le 9$)라고 적힌 블록에 발을 안전하게 디디는 데에는 $t$만큼의 시간이 걸린다. 'X'로 표시된 블록에는 발을 디딜 수 없다. 맨 위 줄에 있는 'T' 블록 중 하나에 어느 한쪽 발이라도 닿으면 오르기가 끝난다.

잭의 이동은 다음 제약을 만족해야 한다. 왼발(또는 오른발)을 어떤 블록에 디딘 다음에는, 반드시 오른발(또는 왼발)만 움직일 수 있다. 즉 두 발은 번갈아 움직인다. 왼발의 위치 $(l_x, l_y)$와 오른발의 위치 $(r_x, r_y)$는 항상 $l_x < r_x$이고 $|l_x - r_x| + |l_y - r_y| \le 3$을 만족해야 한다. 따라서 왼발의 위치가 정해지면, 오른발은 이 조건을 만족하는 9개의 블록 중 하나에 놓아야 한다. 마찬가지로 오른발의 위치가 정해지면, 왼발도 조건을 만족하는 9개의 블록 중 하나에 놓아야 한다.

입력은 여러 개의 데이터셋으로 이루어진다. 입력의 끝은 공백으로 구분된 두 개의 0(0 0)만 있는 줄로 표시된다. 각 데이터셋의 형식은 다음과 같다.

w h
s(1,1) ... s(1,w)
s(2,1) ... s(2,w)
...
s(h,1) ... s(h,w)

정수 $w$와 $h$는 각각 절벽 블록 행렬의 너비와 높이이며, $2 \le w \le 30$, $5 \le h \le 60$이다. 이어지는 $h$개의 줄은 각각 공백으로 구분된 $w$개의 문자로 이루어진다. 문자 $s(y, x)$는 위치 $(x, y)$에 있는 블록의 상태를 나타내며, 그 의미는 다음과 같다.

• 'S': 잭이 오르기를 시작할 수 있는 블록이다.
• 'T': 이 블록에 닿으면 오르기가 끝난다.
• 'X': 발을 디딜 수 없는 블록이다.
• '1'–'9'($= t$): 어느 한쪽 발이든 이 블록에 디디는 데 $t$만큼의 시간이 걸린다.

'S' 또는 'T' 블록에 발을 디디는 데에는 시간이 걸리지 않는다고 가정한다.

각 데이터셋에 대해, 잭이 절벽 오르기를 완료할 수 있는 경우 필요한 최소 시간을 10진 정수 하나만 담은 줄을 출력한다. 완료할 수 없는 경우에는 "-1"만 담은 줄을 출력한다. 각 줄에는 이 숫자 외의 다른 문자가 없어야 한다.