죽음의 비

가로, 세로 길이가 $N$인 정사각형 격자가 있다. 현재 위치와 안전지대 두 곳을 제외한 모든 칸에 체력을 1씩 줄이는 죽음의 비가 내리고 있다. 현재 위치에도 곧 비가 내릴 예정이므로, 죽음의 비를 뚫고 안전지대까지 빨리 이동해야 한다.

격자에는 비를 잠시 막아 주는 우산이 $K$개 있다. 우산마다 내구도 $D$가 있으며, 모든 우산의 내구도는 같다. 우산을 들고 있을 때 비를 맞으면 내구도가 1 줄어들고, 내구도가 0이 되면 우산이 사라진다.

이동은 다음 순서로 진행된다.

1. 상하좌우로 이동한다. 격자 밖으로는 이동할 수 없다.
2. 이동한 칸이 안전지대이면 반복을 종료한다.
3. 이동한 칸에 우산이 있으면 우산을 든다. 이미 우산을 들고 있었다면 그 우산은 버리고 새 우산으로 바꾼다. 버린 우산은 다시 쓸 수 없다.
4. 죽음의 비를 맞으면, 우산을 들고 있을 때는 우산의 내구도가 1 줄고, 우산이 없을 때는 체력이 1 준다.
5. 우산의 내구도가 0이 되면 들고 있던 우산이 사라진다.
6. 체력이 0이 되면 죽는다.
7. 체력이 남아 있다면 안전지대에 도착할 때까지 위 과정을 반복한다.

현재 위치에서 안전지대까지 이동하는 데 필요한 최소 이동 횟수를 구한다.

첫 번째 줄에 격자의 한 변의 길이 $N$, 현재 체력 $H$, 우산의 내구도 $D$가 공백으로 구분되어 주어진다.

다음 $N$개의 줄에는 격자의 각 행이 $N$개의 문자로 붙어서 주어진다. U는 우산, S는 현재 위치, E는 안전지대, .은 빈 칸이다. S와 E는 각각 정확히 1개씩 존재한다.

안전지대까지 이동하는 데 필요한 최소 이동 횟수를 출력한다. 안전지대에 도달할 수 없으면 -1을 출력한다.

$4 \le N \le 500$

$0 \le K \le 10$

$1 \le H \le 10,000$

$1 \le D \le 5,000$

주어지는 모든 수는 정수이다.