UOJ Logo Universal Online Judge

UOJ

#1294. [SCOI2009]围豆豆Bean

统计

Description

Input

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

Output

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

Sample Input

3 8
3
30 -100 30
00000000
010203#0
00000000

Sample Output

38

Hint

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

Source