#include "stdio.h"
#define inf 1000000
#define maxk 32
#define maxc 202
int head[maxk+maxc+2],flag[maxk+maxc+2],level[maxk+maxc+2],n,m,vs,vt,m1,k,c;
int dist[maxk+maxc][maxk+maxc];
struct hp
{
  int c,f,to,next;
}edge[(maxk+maxc+2)*(maxk+maxc+2)];
int bfs()
{
  int i,front,rear,u,v,queue[maxk+maxc];
  memset(flag,0,sizeof(flag));
  flag[vs]=1;
  level[vs]=0;
  front=-1;
  rear=0;
  queue[rear]=vs;
  while(front<rear)
  {
    front++;
    u=queue[front];
    if(u==vt) return 1;
    for(i=head[u];i!=-1;i=edge[i].next)
    {
      v=edge[i].to;
      if(flag[v]==0 && edge[i].c>edge[i].f)
      { 
        flag[v]=1;
        level[v]=level[u]+1;
        rear++;
        queue[rear]=v;
      }
    }
  }
  return 0;
}
int min(int a,int b)
{
  if(a>b) return b;
  return a;
}
int dfs(int u,int a)
{
  int i,v,flow,sum=a;
  if(u==vt) return a;
  for(i=head[u];i!=-1;i=edge[i].next)
  {
    v=edge[i].to;
    if(level[v]==level[u]+1 && edge[i].f<edge[i].c)
    {
      flow=dfs(v,min(a,edge[i].c-edge[i].f));
      edge[i].f+=flow;
      edge[i-1].f-=flow;
      a-=flow;
    }
  }
  return sum-a;
}
void dinic()
{
  while(bfs())
  dfs(vs,inf);
}
void floyd()
{
  int i,j,t;
  for(t=1;t<=k+c;t++)
  for(i=1;i<=k+c;i++)
  for(j=1;j<=k+c;j++)
  if(t!=i && t!=j && dist[i][t]!=inf && dist[t][j]!=inf && dist[i][j]-dist[t][j]>dist[i][t])
  dist[i][j]=dist[t][j]+dist[i][t];
}
void init()
{
  int i,j,dis;
  memset(head,0xff,sizeof(head));
  memset(edge,0,sizeof(edge));
  scanf("%d%d%d",&k,&c,&m);
  for(i=0;i<=(k+c+2)*(k+c+2)-1;i++)
  edge[i].next=-1;
  vs=0;
  vt=k+c+1;
  for(i=1;i<=k+c;i++)
  for(j=1;j<=k+c;j++)
  {
    scanf("%d",&dis);
    if(dis==0) dist[i][j]=inf;
    else dist[i][j]=dis;
  }
  floyd();
  n=k+c;
}
void build(int x)
{
  int m1=0,i,j;
  memset(edge,0,sizeof(edge));
  memset(head,0xff,sizeof(head));
  for(i=1;i<=k;i++)
  {
    edge[m1].c=m;
    edge[m1].next=head[vs];
    edge[m1].to=i;
    head[vs]=m1;
    m1++;
    edge[m1].c=0;
    edge[m1].next=head[i];
    edge[m1].to=vs;
    head[i]=m1;
    m1++;
  }
  for(i=k+1;i<=k+c;i++)
  {
    edge[m1].c=1;
    edge[m1].next=head[i];
    edge[m1].to=vt;
    head[i]=m1;
    m1++;
    edge[m1].c=0;
    edge[m1].next=head[vt];
    edge[m1].to=i;
    head[vt]=m1;
    m1++;
  }
  for(i=1;i<=k;i++)
    for(j=k+1;j<=k+c;j++)
    {
      if(dist[i][j]<=x)
      {
        edge[m1].c=inf;
        edge[m1].next=head[i];
        edge[m1].to=j;
        head[i]=m1;
        m1++;
        edge[m1].c=0;
        edge[m1].next=head[j];
        edge[m1].to=i;
        head[j]=m1;
        m1++;
      }
    }
}
void work()
{
  int t,sign=0,i,j,max=0,min=inf,w,maxflow=0,x;
  for(i=1;i<=n;i++)
  for(j=i+1;j<=n;j++)
  {
    if(dist[i][j]>max && dist[i][j]<inf) max=dist[i][j];
    if(dist[i][j]<min) min=dist[i][j];
  }
  t=m1;
  while(1)
  {
    m1=t;
    x=(max+min)/2;
    build(x);
    dinic();
    maxflow=0;
    for(w=head[vs];w!=-1;w=edge[w].next)
    maxflow+=edge[w].f;
    if(maxflow==c) max=x;
    else  min=x+1;
    if(max==min) break;
  }
  printf("%d",min);
}
int main()
{
  init();
  work();
  return 0;
}