#include <cstdio>

 #include <iostream>

 #include <cstring>

 #include <vector>

 #include <queue>

 #include <algorithm>

 using namespace std;

 #define inf 0x3f3f3f3f

 const int maxn = ;

 struct Edge

 {

     int from,to,cap,flow;

 };

 struct Dinic

 {

     int n,m,s,t;

     vector<Edge> edge;

     vector<int> G[maxn];

     bool vis[maxn];

     int d[maxn];

     int cur[maxn];

     void init()

     {

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

             G[i].clear();

         edge.clear();

         memset(d,,sizeof(d));

         memset(vis,,sizeof(vis));

         memset(cur,,sizeof(cur));

     }

     void AddEdge (int from,int to,int cap)

     {

         edge.push_back((Edge){from,to,cap,});

         edge.push_back((Edge){to,from,,});

         m = edge.size();

         G[from].push_back(m-);

         G[to].push_back(m-);

     }

     bool BFS()

     {

         memset(vis,,sizeof(vis));

         queue<int> Q;

         Q.push(s);

         d[s] = ;

         vis[s] = ;

         while(!Q.empty())

         {

             int x = Q.front();

             Q.pop();

             for(int i=; i<G[x].size(); i++)

             {

                 Edge & e = edge[G[x][i]];

                 if(!vis[e.to]&&e.cap>e.flow)

                 {

                     vis[e.to] = ;

                     d[e.to] = d[x] + ;

                     Q.push(e.to);

                 }

             }

         }

         return vis[t];

     }

     long long DFS(int x,int a)

     {

         if(x==t||a==) return a;

         long long flow = ,f;

         for(int & i = cur[x]; i<G[x].size(); i++)

         {

             Edge & e = edge[G[x][i]];

             if(d[x] + ==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>)

             {

                 e.flow +=f;

                 edge[G[x][i]^].flow -=f;

                 flow +=f;

                 a-=f;

                 if(a==) break;

             }

         }

         return flow;

     }

     int Maxflow (int s,int t) {

         this->s = s;this->t = t;

         int flow = ;

         while(BFS()) {

             memset(cur,,sizeof(cur));

             flow+=DFS(s,inf);

         }

         return flow;

     }

 }sol;

 int dist[maxn][maxn];

 int main()

 {

     int k,c,m;

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

     {

         int l = inf,r=;

         int z = k+c;

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

         {

             for(int j=; j<=z; j++)

             {

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

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

                 {

                     dist[j][i] = inf;

                 }

             }

         }

         for(int kk=; kk<=z; kk++)

         {

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

             {

                 for(int j=; j<=z; j++)

                 {

                     if(dist[k][j]<inf&&dist[i][j]>dist[i][k]+dist[k][j])

                     dist[i][j] =dist[i][kk]+dist[kk][j];

                 }

             }

         }

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

         {

             for(int j=i+; j<=z; j++)

             {

                 if(dist[i][j]<inf)

                     l = min(l,dist[i][j]),r = max(r,dist[i][j]);

             }

         }

         int s = ,t=z+;

         while(l<r)

         {

             int mid = l+(r-l)/;

             sol.init();

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

                 sol.AddEdge(s,i,);

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

                     if(dist[i][j]<=mid) {

                         sol.AddEdge(i,j,inf);

                         sol.AddEdge(j,i,inf);

                     }

                 }

             }

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

                 sol.AddEdge(i,t,m);

             if(sol.Maxflow(,z+)>=c)

             {

                 r = mid;

             }

             else l = mid+;

         }

         printf("%d\n",l);

     }

     return ;

 }