Xor-Mul Chessboard
时间限制：10s 空间限制：128MB
题目描述
一个n*m的棋盘，左上角为(1,1),右下角为(n,m)。相邻的2点之间有连边（如下图中实线）特殊地，(1,i)与(n,i)也连有一条边（如下图中虚线）,i=1..m。
如下图，就是一个n=3,m=4 的棋盘。
输入格式
第一行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
提示
对于100%的数据 2<=n<=5 1<=m<=10000
a,b,c的值均为不大于10^6的正整数。
题目来源
状态压缩动态规划