얼음 미로

탐험가 테라는 얼음 미로에 갇혔다. 얼음 미로의 바닥은 빙판으로 되어 있어서 발을 내디디면 바위에 부딪힐 때까지 미끄러진다. 예를 들어 위 그림에서 테라가 왼쪽으로 이동하면 중간에 멈출 수 없고 왼쪽 바위에 부딪힐 때까지 미끄러진다. 얼음 미로 바깥은 절벽이라서 한 번 빠지면 탈출할 수 없다.

얼음 미로에는 $4$가지 오브젝트가 있다.

1. 테라: 얼음 미로에 갇힌 탐험가다. 상하좌우 4방향으로 이동할 수 있다. 얼음 미로에 테라는 단 1명만 있다. 테라가 처음 위치한 빙판의 미끌 시간은 0이다.
2. 바위: 통과할 수 없다. 미끄러지다가 바위에 부딪히면 그 앞에서 멈춘다.
3. 구멍: 이곳에 빠지면 영영 탈출할 수 없다.
4. 출구: 이곳에 들어가는 즉시 얼음 미로를 탈출한다. 얼음 미로에 출구는 단 1개만 있다.

빙판 위를 미끄러지는 데 걸리는 시간을 미끌 시간이라고 한다. 빙판마다 미끌 시간은 다를 수 있다.

테라가 한쪽 방향으로 이동할 때, 미끄러지는 동안 지나는 빙판들의 미끌 시간을 더하면 이동 시간을 구할 수 있다. 이동 시간 계산에는 다음 두 가지 규칙이 있다.

• 테라가 한쪽 방향으로 이동을 시작할 때, 시작 빙판의 미끌 시간은 포함하지 않는다.
• 테라가 출구로 들어갈 때, 출구 빙판의 미끌 시간은 포함하지 않는다.

위 그림에서 테라가 위로 이동할 때의 이동 시간을 계산해 보자. 테라가 서 있는 시작 빙판의 미끌 시간 4와 출구 빙판의 미끌 시간 0을 제외하면 1 + 2 = 3의 시간이 걸린 뒤 출구를 통해 탈출한다.

저체온증이 시작된 테라는 얼음 미로를 가능한 한 빨리 탈출하고 싶어 한다. 얼음 미로를 탈출하는 데 걸리는 최단 시간을 구하라.

첫 번째 줄에는 얼음 미로의 가로 크기를 나타내는 정수 W ($2 \le W \le 500$)와 세로 크기를 나타내는 정수 H ($2 \le H \le 500$)가 주어진다.

두 번째 줄부터 H개의 줄에 걸쳐 얼음 미로에 대한 정보가 주어진다.

테라는 T, 바위는 R, 구멍은 H, 출구는 E로 나타낸다.

빙판의 미끌 시간 t는 0 이상 9 이하의 정수로 나타낸다.

얼음 미로를 탈출할 수 있다면 최단 탈출 시간을 출력한다.

얼음 미로를 탈출할 수 없다면 -1을 출력한다.