背景 Background

聚会的尾声，所有的朋友都纷纷离去，只剩下飘飘乎居士还陪着candy

描述 Description

candy拿出了自己的糖果阵给飘飘乎居士破解（因为candy最崇拜飘飘乎居士了）。糖果阵被划分成了一个n*m的地区，上面共有p个糖果点，candy给每个糖果点都放置了一个香甜可口的糖果，并且每个糖果都有一个美味度vi。现在飘飘乎居士从左上角出发，他每秒钟可以向相邻的4个方向移动一格。由于某种原因，每个糖果的美味度每秒钟都会下降wi点。甚至当走到某个糖果点时，美味度可能变成了负数，即使这样，飘飘乎居士也想把所有的糖果全部吃到。所以，你的任务是帮助飘飘乎居士计算能够品尝到的糖果的最大美味度。

输入格式 Input Format

第一行3个正整数 n m p

接下来一个n*m的矩阵，出现大写字母’A’到’Z’（对应下面的编号分别为1 2…26）则表示糖果点，不是糖果点的地方用‘.’代表。数据保证不会出现跳字母，也就是A C没有B的情况。

在下来一共p行，每行2个正整数，vi和wi，代表相应的糖果点的美味度和每秒钟减少的美味度.

输出格式 Output Format

一行，代表能够品尝到的最大美味度

样例输入 Sample Input

5 5 3
...A.
..C..
.....
.....
B....
10 1
30 4
10 1

样例输出 Sample Output

14

注释 Hint

样例说明：开始时，A地区糖果的美味度是10，B地区糖果的美味度是30，C地区糖果的美味度是10。飘飘乎居士从（1,1）出发，先走到B点，一共耗时4s，所有的糖果美味度都减少了4*wi，A地区糖果美味度变成了6，B地区糖果变成了14，C地区糖果美味度变成了6，此时得到的美味度是14。接下来走到C地区，耗时5s，此时A地和B地糖果的美味度都变成了1，所以总的美味度是15，最后走到A地，A地区糖果美味度为-1，所以最后的答案是14。

对于40%的数据 0<n m<=10, 0<p<=9

对于100%的数据 0<n m<=100, 0<p<=13

所有数据中0<vi wi<=10000

友情提示：答案可能出现负数

来源 Source

来源 飘飘乎居士——Violet Hill