$\color{red}\texttt{Z}\color{orange}\texttt{B}\color{green}\texttt{O}\color{cyan}\texttt{J}\color{black}-\texttt{P1023}$

$\texttt{Play Game II}$

$\texttt{Description}$

在紧张的比赛过后，$\color{gray}\texttt{zombie462}$ 打开了一款叫 $\texttt{QQ}$ 超市的游戏。

我们将这个游戏的规则稍作改动：游戏的目标是布置货架，使得该摆放方式的总售货能力最大。每个货架的售货能力是给定的，并且货架的摆放方式也是给定的。一个货架在没有宝石的时候仅能对货架朝向的且相邻的一个格子售货（货架仅能朝向上，下，左，右）。总售货能力是在从起点到终点的最短路径中（货架会阻挡路径），周围货架可用的售货能力值总和。

现在给出 $\color{gray}\texttt{zombie462}$ 最初的货架摆放方式，并且他有 $n$ 个多面宝石，$m$ 个售货宝石。每颗宝石都有一个权值 $p$，多面宝石的权值仅能为 $1,2,3$，分别表示双面宝石，四面宝石，八面宝石，而售货宝石的权值可以为任何一个长整型正整数。

售货宝石可以使一个货架售货能力提高 $p$。

双面宝石可以使货架不仅能对朝向格子起作用，还能对朝向相反的相邻的那个格子起作用。

同理，四面宝石可以对上、下、左、右四个方向的相邻的格子起作用，八面宝石可以对周边一圈格子起作用，如图所示。

xxxxxxxxxx
S表示货架朝向格子，A表示可售货格子（事实上，S也算作可售货格子），*表示空格子，#表示货架。
没有宝石：
***
*#*
*S*
镶嵌双面/四面/八面宝石后
*A*  *A*  AAA
*#*  A#A  A#A
*S*  *S*  ASA

一个货架最多可以镶嵌一颗售货宝石，最多可以镶嵌不同种类的多面宝石各一颗。各种多面宝石的效果可以互相叠加，比如同时镶嵌双面和四面宝石，那么至多可以有 $6$ 倍的售货量。

现在请求出所有宝石镶嵌方案中，所能得到的最大总售货能力。注意，货架的朝向可以由你决定。

$\texttt{Input Format}$

第 $1$ 行两个数，$R,C$，表示超市的规模。

第 $2\to R+1$ 行，每行 $C$ 个字符，描述了一种货架摆放方式。

xxxxxxxxxx
图例：
1~9  表明这是个货架，售货能力即为这个数值。
0    表明这个格子为空。
超市起点为(1,1)，终点为(R,C)。

第 $R+2$ 行，两个数 $n,m$，表示两种宝石的数量。

第 $R+3$ 行，$n$ 个数，表示多面宝石的权值。

第 $R+4$ 行，$m$ 个数，表示售货宝石的权值。

$\texttt{Output Format}$

仅一个数，表示最大总售货能力。

$\texttt{Sample}$

$\texttt{Input 1}$

xxxxxxxxxx
3 3
010
021
000
0 0

$\texttt{Output 1}$

xxxxxxxxxx
4

$\texttt{Input 2}$

xxxxxxxxxx
3 3
010
021
000
1 1
3
5

$\texttt{Output 2}$

xxxxxxxxxx
37

$\texttt{Input 3}$

xxxxxxxxxx
4 4
0000
1110
9000
9000
1 1
3
5

$\texttt{Output 3}$

xxxxxxxxxx
32

$\texttt{Hint}$

对于样例二，将两颗宝石全部镶嵌到 $(2,2)$ 位置。

对于样例三，将两颗宝石全部镶嵌到 $(2,3)$ 位置。

对于20%的数据，$n=m=0$。

对于30%的数据，$m=0$。

对于50%的数据，$R,C\leq 100,n,m\leq 30$。

对于100%的数据，$3\leq R,C\leq 500,n,m\leq 1000$，保证有路线可以从起点通往终点，且只有一条最短路线。

答案保证小于 $2^{31}-1$。