【解题思路】

　　显然，这题的答案是这个网格图的最小割。根据最大流-最小割定理，我们可以用网络流算法来求其最小割，时间复杂度最小为O(V2√E)。

　　特殊的，这个网格图是一个平面图，于是可以根据平面图最小割-最短路定理，转化为其对偶图的最短路，时间复杂度最小为O(kE)或O(Vlog2V)（民科算法spfa前途不可估量）。

【参考代码】

　　恩，听说这题我当初RE得生活不能自理，于是直接贴了orz::hzwer大神的代码。。

　　贴个T掉的SAP板子。。（已修正了假板子的当前弧优化。。但还是T得生活不能自理。。）

#pragma GCC optimize(2)
#include
#include
#include
#define REP(i,low,high) for(register int i=(low);i<=(high);++i)
#define INF (0x7f7f7f7f)
#define function(type) __attribute__((optimize("-O2"))) inline type
#define procedure __attribute__((optimize("-O2"))) inline void
using namespace std;

//ex_cmp {
template
inline bool getcmp(T&target,const T&pattern,Compare comp)
{
return comp(pattern,target)?target=pattern,:;
}
//} ex_cmp

//quick_io {
#include
#include
function(int) getint()
{
char c=getchar(); for(;!isdigit(c)&&c!='-';c=getchar());
short s=; for(;c=='-';c=getchar()) s*=-; int r=;
for(;isdigit(c);c=getchar()) r=(r<<)+(r<<)+c-'';
return s*r;
}
//} quick_io

static const int N=,M=; static int cardE=;

struct edge
{
int fr,to,cap;
edge(const int&f=,const int&t=,const int&c=)
:fr(f),to(t),cap(c) {}
}edg[(M<<)+];

int hed[N+],nxt[(M<<)+],hsh[][];

procedure add_edge(const int&fr,const int&to,const int&cp)
{
edg[cardE]=edge(fr,to,cp),nxt[cardE]=hed[fr],hed[fr]=cardE++;
}

//SAP {
int aug[N+],cur[N+],dis[N+],gap[N+],path[N+];

function(int) augment(const int&S,const int&T)
{
for(register int i=T;i!=S;i=edg[path[i]].fr)
{
edg[path[i]].cap-=aug[T],edg[path[i]^].cap+=aug[T];
}
return aug[T];
}

function(int) SAP(const int&S,const int&T,const int&N)
{
memset(aug,,sizeof aug),memset(gap,,sizeof gap);
memset(dis,,sizeof dis); REP(i,,N) cur[i]=hed[i];
aug[S]=INF,gap[]=N; int ret=;
for(register int fr=S;dis[S]());
}
++gap[dis[fr]],cur[fr]=hed[fr];
if(fr!=S) fr=edg[path[fr]].fr;
}
}
return ret;
}
//} SAP

int main()
{
int n=getint(),m=getint(),cardP=;
REP(i,,n) REP(j,,m) hsh[i][j]=++cardP;
memset(hed,-,sizeof hed),memset(nxt,-,sizeof nxt);
REP(i,,n) REP(j,,m)
{
int w=getint();
add_edge(hsh[i][j-],hsh[i][j],w),
add_edge(hsh[i][j],hsh[i][j-],w);
}
REP(i,,n) REP(j,,m)
{
int w=getint();
add_edge(hsh[i-][j],hsh[i][j],w),
add_edge(hsh[i][j],hsh[i-][j],w);
}
REP(i,,n) REP(j,,m)
{
int w=getint();
add_edge(hsh[i-][j-],hsh[i][j],w),
add_edge(hsh[i][j],hsh[i-][j-],w);
}
printf("%d\n",SAP(,cardP,cardP));
return ;
}

　　然后对偶图最短路。。（被队列长度卡了好久。。用了循环队列才过。。）

#pragma GCC optimize(2)
#include
#include
#include
#define REP(i,low,high) for(register int i=(low);i<=(high);++i)
#define INF (0x3f3f3f3f)
#define function(type) __attribute__((optimize("-O2"))) inline type
#define procedure __attribute__((optimize("-O2"))) inline void
using namespace std;

//ex_cmp {
template
inline bool getcmp(T&target,const T&pattern,Compare comp)
{
return comp(pattern,target)?target=pattern,:;
}
//} ex_cmp

//quick_io {
#include
#include
function(long long) getint()
{
char c=getchar(); for(;!isdigit(c)&&c!='+'&&c!='-';c=getchar());
short s=; for(;c=='+'||c=='-';c=getchar()) if(c=='-') s*=-;
long long r=; for(;isdigit(c);c=getchar()) r=(r<<)+(r<<)+c-'';
return s*r;
}
//} quick_io

static const int N=,M=,SIZE=(N<<)+;

struct edge
{
int to,cap; edge(const int&t=,const int&c=):to(t),cap(c) {}
}edg[(M<<)+];

static int cardE=; int hed[N+],nxt[(M<<)+];

procedure add_edge(const int&fr,const int&to,const int&cp)
{
edg[++cardE]=edge(to,cp),nxt[cardE]=hed[fr],hed[fr]=cardE;
}

//SPFA {
bool inq[N+]={}; int dis[N+]={},q[SIZE];

function(int&) move(int&n) {return ++n==SIZE?n=:n;}

function(int) SPFA(const int&S,const int&T)
{
memset(dis,0x3f,sizeof dis),inq[q[dis[S]=]=S]=;
for(register int head=-,tail=;head!=tail;)
{
int fr=q[move(head)];
for(register int i=hed[fr];i;i=nxt[i])
{
int to=edg[i].to;
if(
getcmp(dis[to],dis[fr]+edg[i].cap,less())
&&!inq[to]
) inq[q[move(tail)]=to]=;
}
inq[fr]=;
}
return dis[T];
}
//} SPFA

int main()
{
int n=getint(),m=getint(),nm=(n-)*(m-)<<; if(n==||m==) { int ans=INF; REP(i,,max(m,n)-) getcmp(ans,(int)getint(),less());
return printf("%d\n",ans),;
}
REP(i,,m-)
{
int w=getint(); add_edge(i,nm+,w),add_edge(nm+,i,w);
}
REP(i,,n-) REP(j,,m-)
{
int w=getint(),fr=(i<<)*(m-)+j,to=fr-m+;
add_edge(fr,to,w),add_edge(to,fr,w);
}
REP(i,,m-)
{
int w=getint(),tmp=((n<<)-)*(m-)+i;
add_edge(,tmp,w),add_edge(tmp,,w);
}
REP(i,,n-)
{
int w=getint(),tmp=(i<<)*(m-)+m;
add_edge(,tmp,w),add_edge(tmp,,w);
REP(j,,m-)
{
int fr=(i<<)*(m-)+j-,to=fr+m;
add_edge(fr,to,w=getint()),add_edge(to,fr,w);
}
tmp=(m-)*(i<<|),w=getint(),
add_edge(tmp,nm+,w),add_edge(nm+,tmp,w);
}
REP(i,,n-) REP(j,,m-)
{
int w=getint(),fr=(i<<)*(m-)+j,to=fr+m-;
add_edge(fr,to,w),add_edge(to,fr,w);
}
printf("%d\n",SPFA(,nm+));
return ;
}