스택 미로

미로는 가로 $W$칸, 세로 $H$칸인 격자다. 왼쪽 위 칸을 $(1, 1)$, 오른쪽 아래 칸을 $(W, H)$로 나타낸다. 지금 $(1, 1)$에 있고 $(W, H)$까지 가야 하는데, 이동은 오른쪽으로 한 칸 또는 아래로 한 칸만 할 수 있다.

다음은 미로의 한 예다.

...#......
a###.#####
.bc...A...
##.#C#d#.#
.#B#.#.###
.#...#e.D.
.#A..###.#
..e.c#..E.
####d###.#
#....#.#.#
##E...d.C.

미로의 어떤 칸은 비어 있고(.), 어떤 칸은 바위가 막고 있다(#). 바위 칸에는 들어갈 수 없다. 빈 칸 중 일부에는 보석이 놓여 있고(소문자), 일부에는 보석을 끼우는 구멍이 있다(대문자). 알파벳이 다르면 보석의 종류도 다르다. 즉 a 칸에는 A 종류의 보석이 있고, A 칸에는 A 종류의 보석을 끼우는 구멍이 있다. 보석을 맞는 구멍에 끼우면 좋은 일이 생긴다고 한다.

보석이 있는 칸에서는 그 보석을 집을지 말지 고를 수 있다. 구멍이 있는 칸에서는 가진 보석을 끼울지 말지 고를 수 있다. 처음에는 보석이 하나도 없다. 가방은 아주 커서 보석을 몇 개든 넣을 수 있다. 대신 가방은 스택이라, 가장 마지막에 집은 보석만 꺼내서 끼울 수 있다.

$(1, 1)$에서 $(W, H)$까지 가는 동안 맞는 구멍에 끼울 수 있는 보석은 최대 몇 개인가?

입력은 여러 개의 데이터 집합으로 이루어진다. 0이 두 개 적힌 줄이 나오면 입력이 끝나고, 그 줄은 데이터 집합이 아니다.

각 데이터 집합의 형식은 다음과 같다.

H W
C11C12...C1W
C21C22...C2W
...
CH1CH2...CHW

$H$와 $W$는 격자의 세로와 가로 크기이고, $1 \le W, H \le 50$이다. 이어지는 $H$개의 줄에는 각각 $W$개의 문자가 빈칸 없이 붙어서 온다. $i$번째 줄의 $j$번째 문자 $C_{ij}$는 $i$행 $j$열 칸의 종류를 위에서 설명한 대로 나타낸다. 출발 칸인 1행 1열과 도착 칸인 $H$행 $W$열은 절대 #이 아니다.

한 데이터 집합에서 각 소문자와 각 대문자는 많아야 10번 나온다.

각 데이터 집합마다 맞는 구멍에 끼울 수 있는 보석의 최대 개수를 한 줄에 하나씩 출력한다. $(W, H)$ 칸에 도달할 수 없으면 -1을 출력한다.