4. Xor-Mul 棋盘

【题目描述】

一个 n*m 的棋盘，左上角为(1,1),右下角为(n,m)。相邻的 2 点之间有连边（如下图中实线）特殊地，(1,i)与(n,i)也连有一条边（如下图中虚线）,i=1..m如下图，就是一个 n=3,m=4 的棋盘。

每个点(i,j)给定 2 个值 a[i][j],b[i][j]。每条边 e 给定 1 个值 c[e]。你的任务是给每一个点一个非负的 d 值，最小化(S1+S2)。

大样例

【输入格式】

第一行 2 个整数 n,m。

接着 n 行，每行 m 个数，其中第 i 行第 j 个数表示 a[i][j]。

接着 n 行，每行 m 个数，其中第 i 行第 j 个数表示 b[i][j]。

接着 n 行，每行 m-1 个数，其中第 i 行第 j 个数表示(i,j)与(i,j+1)的边的c 值。

接着 n-1 行，每行 m 个数，其中第 i 行第 j 个数表示(i,j)与(i+1,j)的边的c 值。

最后一行 m 个数，其中第 i 个数表示(1,i)与(n,i)的边的 c 值。

【输出格式】

一个整数，表示 S1+S2 的最小值

【样例输入】

2 2
3 6
7 3
9 9
1 8
9
5
3 9
4 3

【样例输出】

49

【提示】

对于 30%的数据，n=2，m<=100

对于 60%的数据，n<=4，m<=10000

对于 100%的数据，2<=n<=5，1<=m<=10000

a,b,c 的值均为不大于 10^6 的正整数。