Description:


最近房地产商GDOI(Group of Dumbbells Or Idiots)从NOI(Nuts Old Idiots)手中得到了一块开发土地。据了解,这块土地是一块矩形的区域,可以纵横划分为N×M块小区域。GDOI要求将这些区域分为商业区和工业区来开发。根据不同的地形环境,每块小区域建造商业区和工业区能取得不同的经济价值。更具体点,对于第i行第j列的区域,建造商业区将得到Aij收益,建造工业区将得到Bij收益。另外不同的区域连在一起可以得到额外的收益,即如果区域(I,j)相邻(相邻是指两个格子有公共边)有K块(显然K不超过4)类型不同于(I,j)的区域,则这块区域能增加k×Cij收益。经过Tiger.S教授的勘察,收益矩阵A,B,C都已经知道了。你能帮GDOI求出一个收益最大的方案么?

Input:


输入第一行为两个整数,分别为正整数N和M,分别表示区域的行数和列数;第2到N+1列,每行M个整数,表示商业区收益矩阵A;第N+2到2N+1列,每行M个整数,表示工业区收益矩阵B;第2N+2到3N+1行,每行M个整数,表示相邻额外收益矩阵C。第一行,两个整数,分别是n和m(1≤n,m≤100)。任何数字不超过1000”的限制

Output:


输出只有一行,包含一个整数,为最大收益值。

Sample Input:


Sample Output:


题解:


像我这种没有接触过这种类型的最小割的蒟蒻怎么可能自己想得到黑白染色(⊙o⊙)?

黑白染色这个东西吼啊( ⊙ o ⊙ )

我们把整个矩阵黑白相间染色,那么相邻的格子绝对是不同色的。

对于黑格,s向该点连权值为a的边,该点向t连权值为b的边。

对于白格,我们反过来连~

然后两个相邻的格子互相连一条边权为c之和的边。

这样脚妙地构造了最小割~

总权值减去最小割就是答案了~$$≧▽≦)/~

就是比较难想QAQ

代码如下: