감옥 탈출

N×M 크기의 감옥 지도가 있다. 각 칸은 빈 칸(.), 벽(#), 문(@), 열쇠(a~f), 출구(E), 시작 위치(S) 중 하나이다. 문을 열려면 대응하는 열쇠(a→A, b→B, ..., f→F)가 필요하다.

S에서 E까지 최소 이동 횟수로 탈출하시오. 불가능하면 -1을 출력한다.

입력

첫째 줄에 N, M이 주어진다. 다음 N줄에 M개의 문자가 주어진다.

• 1 ≤ N, M ≤ 50
• 열쇠는 af, 문은 AF로 표기

출력

최소 이동 횟수를 출력한다. 불가능하면 -1을 출력한다.

예제 입력

3 4
Sa#E
.A.#
....

예제 출력

6