전자 도로 요금 (ERP)

에로파그니스시는 차가 방향을 바꿀 때마다 요금을 걷는다. 모든 차에는 직진과 좌회전, 우회전, 유턴을 구분해 감지하는 장치가 달려 있고, 장치가 기록한 대로 요금이 부과된다. 좌회전은 $1, 우회전은 $5이고 직진은 무료다. 유턴은 금지되어 있지만 도로 끝에서 직진도 좌회전도 우회전도 더 할 수 없을 때는 예외로 허용한다. 이런 유턴은 한 번에 $10이다.

에로파그니스의 도로는 모두 동서남북 방향으로만 뻗어 있어서 지도를 격자로 나타낼 수 있다. 출발 지점에서 도착 지점까지 가장 싼 경로의 요금을 알려 주는 길 안내 시스템을 만들자.

지도는 문자 격자다. #는 도로 구간이고 .는 도로가 아닌 구간이다. 출발 지점과 도착 지점은 모두 도로 구간 위에 있고, 도로 구간은 양방향으로 지날 수 있다.

차는 항상 도로 구간 한 칸 위에서 네 방향 중 한쪽을 향하고 있다. 이 상태에서 차가 할 수 있는 행동은 다음 네 가지다.

• 직진. 앞 칸이 도로면 그 칸으로 나아간다. 요금은 없고 향하는 방향도 그대로다.
• 좌회전. 왼쪽 칸이 도로면 그 칸으로 들어서서 그 방향을 향한다. 요금은 $1이다.
• 우회전. 오른쪽 칸이 도로면 그 칸으로 들어서서 그 방향을 향한다. 요금은 $5이다.
• 유턴. 앞, 왼쪽, 오른쪽 세 칸이 모두 도로가 아닐 때만 할 수 있다. 뒤 칸으로 돌아 나가고 요금은 $10이다.

회전은 언제나 돌아 들어간 도로 칸으로 차를 옮기므로, 한 칸에서 회전을 연달아 두 번 할 수는 없다.

지도의 높이는 4 이상 30 이하이고 너비도 4 이상 30 이하다. 출발 지점과 도착 지점은 각각 하나씩 있고, 출발 지점에서 도착 지점까지 가는 경로는 항상 존재한다. 지도의 테두리는 모두 .이라서 주어진 지도 밖으로 나갈 일은 없다.

입력은 다음 줄로 이루어진다.

1. 첫째 줄에는 지도의 높이 h와 너비 w가 양의 정수로 주어진다.

2. 이어지는 h개 줄에는 각각 w개의 문자가 주어진다. 각 문자는 다음 중 하나다.

   • .는 도로가 아닌 구간
   • #는 도로 구간
   • E는 차가 동쪽을 향한 출발 지점
   • W는 차가 서쪽을 향한 출발 지점
   • N은 차가 북쪽을 향한 출발 지점
   • S는 차가 남쪽을 향한 출발 지점
   • F는 도착 지점

지도에서 E, W, N, S 중 하나인 문자는 정확히 하나다. 지도의 위쪽이 북쪽이고 오른쪽이 동쪽이다.

출발 지점에서 도착 지점까지 가는 가장 싼 경로의 요금을 한 줄에 출력한다.