题目描述

市长希望建一个 $ n \times m $ 的楼房方阵。第 $ i $ 行第 $ j $ 列的楼房高度必须在 $ l_{i,j} $ 与 $ r_{i,j} $ 之间。

因为每一块地皮的价格不同，若第 $ i $ 行第 $ j $ 列的楼房高度为 $ x $ 则可以获得 $ a_{i,j} \times x $ 的利润。

楼房的产值与采光也有关系，对于第 $ i $ 行第 $ j $ 列的楼房，每有一栋与其相邻的楼房高度比它低 $ x $，就可以额外获得 $ b_{i,j} \times x $ 的利润。

注：这里的相邻指的是在方格图上有公共边，一栋楼房的采光利润为所有比它更低的相邻的楼房对它的采光利润的贡献之和。

市长希望修建这些房子所获得的总利润最大，现在求出这个值吧。

输入格式

第一行两个整数 $n,m$，表示楼房矩阵的长宽。

接下来 $4$ 个 $n\times m$ 的矩阵，分别代表 $l,r,a,b$ 数组。

输出格式

一行一个整数，表示最大获利。

输入输出样例 #1

输入 #1

1 2
1 1
10 10
5 3
1 9

输出 #1

116

数据规模与约定

对于 $100\%$ 的数据，$ 1 \leq n, m \leq 50, 1 \leq l_{i,j} \leq r_{i,j} \leq 100, 1 \leq a_{i,j}, b_{i,j} \leq 10^9 $。

本题采用捆绑测试，每个 Subtask 的具体分值如下：

$$ \begin{array}{|c|c|c|} \hline \bf 子任务 & \bf 特殊性质 & \bf 分值\\ \hline 1 & 1 \leq n, m \leq 4, 1 \leq l_{i,j} \leq r_{i,j} \leq 2 & 10\\ \hline 2 & 1 \leq n, m \leq 10, 1 \leq l_{i,j} \leq r_{i,j} \leq 100 & 30\\ \hline 3 & 无 & 60\\ \hline \end{array} $$