#include<iostream> #include<cstring> #include<cstdio> #define INF 0x7fffffff using namespace std; struct data{ int from,to,next,v,c; }e[500001]; int n,m,k,cnt=1,ans,tot,head[30001],from[30001],q[30001],dis[30001]; bool inq[30001]; void insert(int u,int v,int w,int c){ e[++cnt].from=u; e[cnt].to=v; e[cnt].v=w; e[cnt].c=c; e[cnt].next=head[u]; head[u]=cnt; } void ins(int u,int v,int w,int c){ insert(u,v,w,c); insert(v,u,0,-c); } bool spfa(){ int t=0,w=1,i,now; memset(dis,-1,sizeof(dis)); q[0]=dis[0]=0;inq[0]=true; while(t<w){ now=q[t++];i=head[now]; while(i){ if(e[i].v>0&&dis[e[i].to]<dis[now]+e[i].c){ dis[e[i].to]=dis[now]+e[i].c; from[e[i].to]=i; if(!inq[e[i].to]){ inq[e[i].to]=true; q[w++]=e[i].to; } } i=e[i].next; } inq[now]=false; } if(dis[3000]==-1)return false; else return true; } void mcf(){ int i=from[3000],x=INF; while(i){ x=min(x,e[i].v); i=from[e[i].from]; } i=from[3000]; while(i){ e[i].v-=x;e[i^1].v+=x; ans+=x*e[i].c; i=from[e[i].from]; } } int main(){ scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) for(int j=1;j<=m+i-1;j++){ int t;scanf("%d",&t);tot++; ins(tot,tot+1501,1,t); if(i<n){ ins(tot+1501,tot+i+m,1,0); ins(tot+1501,tot+i+m-1,1,0); } } for(int i=1;i<=m;i++)ins(0,i,1,0); for(int i=1;i<=n+m-1;i++)ins(tot-i+1502,3000,1,0); for(int i=1;i<=k;i++)if(spfa())mcf();else break; printf("%d",ans); return 0; }