小学生网格题

题目描述

n*m四联通的网格,一个格子被控制满足下面两个条件之一:\ 1:这个格子被标记\ 2:这个格子相邻的格子都被标记\ 给出每个格子控制的收益和标记的代价,求最大收益-代价

输入输出格式

输入格式


第一行两个数,表示$n,m$\ 接下来一个$n*m$的矩阵,表示代价\ 接下来一个$n*m$的矩阵,表示收益\ 矩阵中元素的意义如下:\ 1~9表示1~9\ a~z表示10~35\ A~Z表示36~61\ 除此之外没有其他元素

输出格式


一行,表示最大的收益-代价

输入输出样例

输入样例 #1

5 5
198Dn
t9f0j
3n7Y5
19zwr
Q4KZG
N9nBX
9kz8X
hLms3
A58Rs
QPCzV

输出样例 #1

598

输入样例 #2

3 3
aaa
aaa
aaa
111
111
111

输出样例 #2

0

输入样例 #3

5 4
NccK
9nwg
nuS2
ow2K
pjV1
11zK
1d48
J7xJ
RV81
rUsG

输出样例 #3

352

说明

对于样例二,什么都不选就是最优答案\ $1\le n,m \le100$