Description

西游记的故事已经过去400多年了。如今盼盼想重走西游路。费尽千辛万苦，盼盼终于找到一份记录了当年西游记的时候所走路线的地图，为了方便理解盼盼将该地图等效成网格图。地图中包含多个国家（国家信息以字母或数字表示，区分大小写），据可靠消息，通过这些国家需要某个特定国家的通关文牒。而且，这些国家所需要的通关文碟不一定相同。通过一个国家后，会获得对应该国家编号的通关文牒。例如：到达国家A，需要通关文牒a（通过国家a获得）。通过该国家后，盼盼会获得国家A的通关文牒，即通关文牒A。特别的，通过大唐和雷音寺时不需要任何的通关文牒，通过大唐后可以获得通关文碟T。由于一些特殊的因素，盼盼只能携带一种通关文牒上路。经过某一个国家的时候，他可以选择是否更换已拥有的通关文碟。盼盼从大唐出发，出发时具有通关文牒T；盼盼想知道，根据地图上所示，从大唐出发，他最少需要多少步到达雷音寺。

Input Format

第一行输入三个整数$n, m, k$（$2 \le n , m \le 500, 0\le k \le 60$）表示地图的大小和城市的个数。接下来$n$行输入地图。其中：'L'表示雷音寺； 'T'表示大唐； '#'表示不能行走的地方；'.'表示路；除了'T'和'L'以外的字母或数字代表其他国家。接下来k行，输入2个字符，前一个字符表示一个国家，后一个字符表示通过该国家所需要的通关文碟种类。

Output Format

输出一个整数，表示从大唐走到雷音寺的最少步数。

5 5 3
T....
.##..
1#.2.
##.#.
L..3.
1 T
2 T
3 2

10

8 10 4
L#D##.....
.s.#.#..#.
.#.#...##.
.#.b...#T.
.#.#.#...a
.#.#......
.#.#..#...
...#....#.
a T
b a
D a
s D

17

Source

1816 Online Judge 10.100.0.232