#include<cstring>

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<queue>

 using namespace std;

 int map[][];

 const int INF=;

 struct Node{

     int c;

     int f;

 }ma[][];

 int m,c,knum,pre[];

 int sx,se;

 void Floy(){

     for(int k=;k<=knum+c;k++)

        for(int i=;i<=c+knum;i++)

            for(int j=;j<=c+knum;j++){

                if(k!=i&&i!=j&&k!=j&&map[i][k]+map[k][j]<map[i][j])

                    map[i][j]=map[i][k]+map[k][j];

            }

 }

 bool  BFS(){

     memset(pre,,sizeof(pre));

     queue<int>Q;

     Q.push(sx);

     pre[sx]=;

     while(!Q.empty()){

         int d=Q.front();

         Q.pop();

         for(int i=;i<=knum+c+;i++){

             if(!pre[i]&&ma[d][i].c-ma[d][i].f){

             pre[i]=pre[d]+;

             Q.push(i);

             }

         }

     }

     return pre[se]!=;

 }

 int dinic(int pos,int flow){

     int f=flow;

      if(pos==se)

        return flow;

      for(int i=;i<=c+knum+;i++){

            if(ma[pos][i].c-ma[pos][i].f&&pre[i]==pre[pos]+){

                 int a=ma[pos][i].c-ma[pos][i].f;

                 int t=dinic(i,min(a,flow));

                 ma[pos][i].f+=t;

                 ma[i][pos].f-=t;

                 flow-=t;

                 if(flow<=)break;

                 }

        }

        if(f-flow<=)pre[pos]=-;

     return f-flow;

 }

 int sum(){

      int s=;

     while(BFS())

        s+=dinic(sx,INF);

        return s;

 }

 void build(int maxn){

     memset(ma,,sizeof(ma));

    for(int i=knum+;i<=knum+c;i++)

          ma[][i].c=;

    for(int i=;i<=knum;i++)

          ma[i][se].c=m;

    for(int i=knum+;i<=c+knum;i++)

        for(int j=;j<=knum;j++){

               if(map[i][j]<=maxn)

                   ma[i][j].c=;

            }

 }

 int dinic2(int maxn) {

     int maxflow;

     int low=,mid,up=maxn;

     while(low<=up){

         mid=(low+up)>>;

        build(mid);

         maxflow=;

        maxflow=sum();

         if(maxflow<c)low=mid+;

         else

             up=mid-;

     }

     return up+;

 }

 int main(){

     int maxn;

     while(~scanf("%d%d%d",&knum,&c,&m)){

         sx=;se=knum+c+;

         maxn=;

         for(int i=;i<=knum+c;i++)

           for(int j=;j<=knum+c;j++){

                scanf("%d",&map[i][j]);

                if(map[i][j]==)

                   map[i][j]=INF;

           }

              Floy();

           for(int i=;i<=knum+c;i++)

             for(int j=;j<=knum+c;j++)

                if(map[i][j]<INF&&map[i][j]>maxn)

                    maxn=map[i][j];

              printf("%d\n",dinic2(maxn));

         }

 }