题目描述

小 N 手上有一个 $n \times m$ 的方格图，控制某一个点要付出 $a_{i,j}$ 的代价，然后某个点如果被控制了，或者他周围的所有点（上下左右）都被控制了，那么他就算是被选择了的。一个点如果被选择了，那么可以得到 $b_{i,j}$ 的回报，现在请你帮小N选一个最优的方案，使得回报-代价尽可能大。

输入格式

第一行两个正整数 $n,m$ 表示方格图的长与宽。
接下来 $n$ 行每行 $m$ 个正整数 $a_{i,j}$ 表示控制的代价。
接下来 $n$ 行每行 $m$ 个正整数 $b_{i,j}$ 表示选择的回报。

输出格式

一个整数，表示最大的回报 $-$ 代价（如果一个都不控制那么就是 $0$）。

3 3
1 100 100
100 1 100
1 100 100
2 0 0
5 2 0
2 0 0

8

数据规模与约定

对于 $100\%$ 的数据，$n,m \le 50$，$a_{i,j},b_{i,j} \le 100$。