问题描述

有一个迷宫，可以用一个 $W \times 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)$ 的路上，你能够将多少个宝石放入正确的洞中？

输入

输入包含一个数据集序列。输入的末尾由一行包含两个零表示。每个数据集的格式如下。

$H$ $W$ $C_{11}$ $C_{12}$ ... $C_{1W}$ $C_{21}$ $C_{22}$ ... $C_{2W}$ ... $C_{H1}$ $C_{H2}$ ... $C_{HW}$

这里，$H$ 和 $W$ 是网格的高度和宽度。你可以假设 $1 \leq W, H \leq 50$。数据集的其余部分由 $H$ 行组成，每行由 $W$ 个字母组成。每个字母 $C_{ij}$ 指定了单元格 $(i, j)$ 的类型，如前所述。保证 $C_{11}$ 和 $C_{WH}$ 永远不是#。

你还可以假设每个小写或大写字母在每个数据集中最多出现 10 次。

输出

对于每个数据集，输出你能够将宝石放入对应洞中的最大数量。如果你无法到达单元格 $(W, H)$，则输出 -1。

示例输入

3 3
ac#
b#C
.BA
3 3
aaZ
a#Z
aZZ
3 3
..#
.#.
#..
1 50
abcdefghijklmnopqrstuvwxyYXWVUTSRQPONMLKJIHGFEDCBA
1 50
aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyY
1 50
abcdefghijklmnopqrstuvwxyABCDEFGHIJKLMNOPQRSTUVWXY
1 50
aaaaaaaaaabbbbbbbbbbcccccCCCCCBBBBBBBBBBAAAAAAAAAA
10 10
...#......
a###.#####
.bc...A...
##.#C#d#.#
.#B#.#.###
.#...#e.D.
.#A..###.#
..e.c#..E.
####d###.#
##E...D.C.
0 0

示例输入的输出

2
0
-1
25
25
1
25
4

来源名称

JAG Practice Contest for ACM-ICPC Asia Regional 2012