题目描述

一个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值。 2<=n<=5， 1<=m<=10000 a,b,c 的值均为不大于 10^6 的正整数

输出格式

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

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

49

提示

没有写明提示

题目来源

没有写明来源