32360번 - 더워!

문제

한여름의 날씨는 더워도 너무 덥다. 민규는 외출은커녕 집에서 에어컨에 의지한 채 살아가고 있지만, 오늘은 약속이 있어 불가피하게 집 밖으로 나와 약속 장소로 가야 한다. 그러나 시원한 집에서 쉬다 보니 어느새 약속 시간에 늦어버리고 말았다. 빨리 집을 나서야 한다!

밖은 $N$행 $M$열의 격자로 이루어져 있다. 격자의 각 칸은 집, 약속 장소, 건물, 벽, 길 중 하나로 이루어져 있다. 집과 건물은 실내이고, 길, 벽, 약속 장소는 실외이다.

밖은 너무 더워 실외에 있을 때는 지속적으로 불쾌함 $B$가 증가한다. 그러나 중간중간 이동 경로에 있는 실내는 매우 시원하여, 실내를 지나가거나 실내에서 쉬는 동안에는 불쾌함이 감소한다.

초기에 민규의 불쾌함은 0ドル$이며, 불쾌함이 100ドル$이 되면 민규는 견딜 수 없어 쓰러지고 만다.

민규는 집에서 출발하여 다음과 같은 순서로 행동한다. 1번 행동은 이동 여부와 상관없이 1ドル$의 시간이 소요되며, 2번과 3번 행동에 드는 시간은 무시할 수 있을 만큼 짧다.

1. 격자판 내에서 상하좌우에 있는 벽이 아닌 인접한 칸으로 이동하거나, 이동하지 않고 가만히 있는다.
2. 현재 있는 칸에 따라서 불쾌함이 증가하거나 감소한다.
   • 현재 있는 칸이 실내라면 불쾌함이 $\max(0, B-K)$까지 감소한다.
   • 현재 있는 칸이 실외라면 불쾌함이 $\min(100, B+C)$까지 증가한다.
3. 약속 장소에 도달하거나 불쾌함이 100ドル$이 되면 행동을 멈춘다. 그렇지 않다면 1번으로 돌아간다.

민규가 약속 장소에 쓰러지지 않고 최대한 빠르게 도달할 수 있도록, 민규의 이동 경로를 계산하는 프로그램을 작성해 주자. 단, 약속 장소로 이동하여 불쾌함이 100ドル$이 되면 민규는 쓰러지며, 약속 장소에 도달하지 못한 것으로 간주한다.

입력

첫 번째 줄에 격자의 크기를 나타내는 정수 $N,ドル $M$이 공백으로 구분되어 주어진다.

두 번째 줄에 실내에서 감소하는 불쾌함, 실외에서 증가하는 불쾌함을 나타내는 정수 $K,ドル $C$가 공백으로 구분되어 주어진다.

세 번째 줄부터 $N+2$번째 줄까지 거리의 상태를 나타내는 길이 $M$의 문자열이 주어진다. $i+2$번째 줄의 $j$번째 문자는 $i$행 $j$열의 칸을 이루는 대상을 나타낸다. 만약 문자가 S라면 민규의 집 위치, E라면 약속 장소, H라면 건물, #이라면 벽, .(온점)이라면 길을 의미한다. S와 E는 각각 하나씩 주어진다.

출력

민규가 약속 장소에 쓰러지지 않고 도달할 수 있는 최소 시간을 출력한다. 만약 그런 방법이 없다면 -1을 출력한다.

제한

• 2ドル \leq N, M \leq 100$
• 1ドル \leq K, C \leq 100$
• 0ドル \leq B \leq 100$
• 1ドル \leq i \leq N$
• 1ドル \leq j \leq M$
• $i, j$와 입력으로 주어지는 모든 수는 정수이다.

힌트