리펠

승리의 길 마지막 던전에 들어섰는데 포켓몬의 상태가 좋지 않다. 남은 포켓몬까지 쓰러지면 안 되므로, 야생 포켓몬과 마주치는 횟수를 최대한 줄이면서 던전을 빠져나가려고 한다. 다행히 던전 안에는 리펠을 뿌려 주는 특별한 칸이 있다. 리펠은 정해진 걸음 수 동안 야생 포켓몬을 쫓아내는 냄새다.

이동은 위, 아래, 왼쪽, 오른쪽으로 한 칸씩만 할 수 있다. 규칙은 다음과 같다.

• 입구에서 출발할 때 남은 보호 걸음은 0이다.
• 한 번 이동하는 것이 한 걸음이다. 남은 보호 걸음이 1 이상이면 그 걸음은 리펠의 보호를 받고, 남은 보호 걸음이 1 줄어든다. 남은 보호 걸음이 0이면 그 걸음은 보호를 받지 못한다. 보호받지 못한 걸음으로 야생 포켓몬이 사는 칸에 들어가면 위험한 걸음 한 번으로 센다.
• 걸음을 옮긴 뒤, 도착한 칸이 값 $v$인 리펠 지점이고 남은 보호 걸음이 $v$보다 작으면 남은 보호 걸음이 $v$가 된다. 리펠은 누적되지 않는다. 냄새는 남은 걸음 수가 더 적은 사람에게만 적용된다. 같은 리펠 지점을 다시 밟으면 다시 적용된다.
• 야생 포켓몬은 .으로 표시된 칸에만 산다. 다른 칸에 들어가는 걸음은 보호를 받지 못해도 세지 않는다.

입구에서 출구까지 갈 때 위험한 걸음의 최소 횟수를 구하라.

첫째 줄에 두 정수 $R$, $C$ ($1 \le R, C \le 100$)가 주어진다. 다음 $R$개 줄에는 길이가 $C$인 문자열이 한 줄에 하나씩 주어져 던전을 나타낸다.

• X는 입구다. 여기에서 출발한다.
• Y는 출구다.
• 1부터 9까지와 A부터 F까지의 문자는 리펠 지점이다. 이 문자를 16진수로 읽은 값이 리펠이 지속되는 걸음 수다. 리펠 지점은 최대 100개다.
• .은 야생 포켓몬이 사는 칸이다.
• #은 벽이며 들어갈 수 없다.

입구에서 출구까지 가는 경로는 항상 존재한다.

리펠의 보호 없이 야생 포켓몬이 사는 칸을 밟는 최소 횟수를 한 줄에 출력한다.