#1294. [SCOI2009]围豆豆Bean

题目描述

输入格式

第一行两个整数N和M，为矩阵的边长。 第二行一个整数D，为豆子的总个数。 第三行包含D个整数V1到VD，分别为每颗豆子的分值。 接着N行有一个N×M的字符矩阵来描述游戏矩阵状态，0表示空格，#表示障碍物。而数字1到9分别表示对应编号的豆子。

输出格式

仅包含一个整数，为最高可能获得的分值。

样例

样例输入

3 8  

3  

30 -100 30  

00000000  

010203#0  

00000000  

样例输出

38  

数据范围与提示

50%的数据满足1≤D≤3。
100%的数据满足1≤D≤9，1≤N, M≤10，-10000≤Vi≤10000。