달이 차오르는 미로 탈출

민식이는 직사각형 미로 안에 있다. 미로에서 탈출하려면 출구 칸으로 이동해야 한다. 한 번의 이동은 현재 칸에서 상하좌우로 인접한 한 칸으로 이동하는 것이다.

미로의 각 칸은 다음 중 하나이다.

• 빈 칸 .: 언제나 이동할 수 있다.
• 벽 #: 이동할 수 없다.
• 열쇠 a~f: 언제나 이동할 수 있으며, 처음 들어가면 해당 열쇠를 얻는다.
• 문 A~F: 대응하는 소문자 열쇠를 가진 경우에만 이동할 수 있다.
• 시작 위치 0: 민식이가 처음 서 있는 빈 칸이다.
• 출구 1: 이 칸에 도착하면 미로를 탈출한다.

열쇠는 얻은 뒤 계속 사용할 수 있다. 민식이가 출구 중 하나에 도착하기 위해 필요한 이동 횟수의 최솟값을 구하시오.

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 <= N, M <= 50)

둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 종류의 열쇠나 문이 여러 개 있을 수 있으며, 어떤 문은 대응하는 열쇠가 미로에 없을 수도 있다. 0은 정확히 한 개이고, 1은 한 개 이상 있다. 열쇠는 여러 번 사용할 수 있다.

민식이가 미로를 탈출하는 데 필요한 이동 횟수의 최솟값을 출력한다. 탈출할 수 없으면 -1을 출력한다.