暂无测试数据。

蒜头君是一个乐于助人的好孩子，这天他所在的乡村发生了洪水，有多名村民被困于孤岛上，于是蒜头君决定去背他们离开困境，假设蒜头君所在的村子是 $n \times m$ 的网格，网格中.号代表平地，#号代表该地已被洪水淹没，A、B……等大写字母表示该地有村民被困，s代表蒜头君的起点，t代表蒜头君的终点。

蒜头君的初始速度为 $k$ 秒一格，他每次可以向上下左右 $4$ 个方向中的一个移动 $1$ 格。在背上一个村民后，他的速度可能会降低，也可能会加快，但他的速度不能快于 $1$ 秒每格，那么蒜头君想知道，他最快需要多长时间将所有村民救出？

注意：不能在终点以外的地方放下村民；可以同时背多个村民。

输入格式

第一行 $3$ 个正整数 $n,m,k$，分别表示村庄长度、宽度、蒜头君初始速度。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，表示村庄的地形，字符串意义如上所述。

接下来若干行，每行一个大写字母、一个整数，表示该编号的村民会使 $k$ 增加 / 减少多少。行数等同于地形中大写字母的个数。大写字母按字典序，即A、B、C的顺序排列，保证前后两行的字母是连续的。

输出格式

输出 $1$ 个整数，表示最小用时。

数据规模

对于 $10$% 的数据，满足 $1 \le n,m \le 5$，村民个数为 $1$；

对于 $50$% 的数据，满足 $1\le n,m\le5$，村民个数小于等于 $5$；

对于 $100$% 的数据，满足 $1\le n,m\le10$，村民个数小于等于 $10$。

4 4 2
s.##
..A#
.B##
...t
A -3
B 4

17