#include #include #include #include #define LL long long #define Re register int using namespace std; const int N=2e5,M=2e6+5,inf=2e9; int T,x,y,z,w,G,o=1,p,n,m,h,t,st,ed,maxp,cyf[N],pan[N],pre[N],dis[N],head[N],Map[11][11][11][11];LL mincost,maxflow; struct QAQ{int w,to,next,flow;}a[M<<1];queueQ;vectorkey[11][11]; inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;} inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);} inline int SPFA(Re st,Re ed){ for(Re i=0;i<=ed;++i)dis[i]=inf,pan[i]=0; Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf; while(!Q.empty()){ Re x=Q.front();Q.pop();pan[x]=0; for(Re i=head[x],to;i;i=a[i].next) if(a[i].flow&&dis[to=a[i].to]>dis[x]+a[i].w){ dis[to]=dis[x]+a[i].w,pre[to]=i; cyf[to]=min(cyf[x],a[i].flow); if(!pan[to])pan[to]=1,Q.push(to); } } return dis[ed]!=inf; } inline void EK(Re st,Re ed){ while(SPFA(st,ed)){ Re x=ed;maxflow+=cyf[ed],mincost+=(LL)cyf[ed]*dis[ed]; while(x!=st){ Re i=pre[x]; a[i].flow-=cyf[ed]; a[i^1].flow+=cyf[ed]; x=a[i^1].to; } } } inline int P(Re x,Re y,Re k){return (x-1)*m+y+k*n*m;} int main(){ in(n),in(m),in(p),maxp=(1<>KEY-1)&1))add_(P(i,j,k),P(i,j,k|(1<>Map[i][j][i+1][j]-1)&1)add_(P(i,j,k),P(i+1,j,k),inf,1); } if(j>Map[i][j][i][j+1]-1)&1)add_(P(i,j,k),P(i,j+1,k),inf,1); } if(i>1&&Map[i][j][i-1][j]!=-1){ if(!Map[i][j][i-1][j])add_(P(i,j,k),P(i-1,j,k),inf,1); else if((k>>Map[i][j][i-1][j]-1)&1)add_(P(i,j,k),P(i-1,j,k),inf,1); } if(j>1&&Map[i][j][i][j-1]!=-1){ if(!Map[i][j][i][j-1])add_(P(i,j,k),P(i,j-1,k),inf,1); else if((k>>Map[i][j][i][j-1]-1)&1)add_(P(i,j,k),P(i,j-1,k),inf,1); } } } } else for(Re k=0;k<=maxp;++k){ if(i>Map[i][j][i+1][j]-1)&1)add_(P(i,j,k),P(i+1,j,k),inf,1); } if(j>Map[i][j][i][j+1]-1)&1)add_(P(i,j,k),P(i,j+1,k),inf,1); } if(i>1&&Map[i][j][i-1][j]!=-1){ if(!Map[i][j][i-1][j])add_(P(i,j,k),P(i-1,j,k),inf,1); else if((k>>Map[i][j][i-1][j]-1)&1)add_(P(i,j,k),P(i-1,j,k),inf,1); } if(j>1&&Map[i][j][i][j-1]!=-1){ if(!Map[i][j][i][j-1])add_(P(i,j,k),P(i,j-1,k),inf,1); else if((k>>Map[i][j][i][j-1]-1)&1)add_(P(i,j,k),P(i,j-1,k),inf,1); } } EK(st,ed); if(maxflow)printf("%lld",mincost); else printf("-1"); }