2514: 蒜头君救人

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

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

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

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

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

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

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

17