[SCOI2009]围豆豆Bean

时间限制:10s      空间限制:162MB

题目描述


输入格式

第一行两个整数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。


题目来源

没有写明来源