#include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 255

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 int path[N],flow[N],gh[N][N],st,en;

 int w[N][N];

 int bfs()

 {

     int i;

     memset(path,-,sizeof(path));

     for(i =  ; i <= en ; i++)

     flow[i] = INF;

     queue<int>q;

     q.push();

     while(!q.empty())

     {

         int tk = q.front();

         q.pop();

         if(tk==en)

         break;

         for(i =  ; i <= en ; i++)

         {

             if(path[i]==-&&gh[tk][i])

             {

                 path[i] = tk;

                 flow[i] = min(flow[tk],gh[tk][i]);

                 q.push(i);

             }

         }

     }

     if(path[en]==-)

     return -;

     return flow[en];

 }

 int EK()

 {

     int now,pre,sum=,k;

     while((k=bfs())!=-)

     {

         sum+=k;

         now = en;

         while(now!=st)

         {

             pre = path[now];

             gh[pre][now]-=k;

             gh[now][pre]+=k;

             now = pre;

         }

     }

     return sum;

 }

 int main()

 {

     int k,c,i,g,j,m;

     while(scanf("%d%d%d",&k,&c,&m)!=EOF)

     {

         int n = k+c;

         for(i = ; i <= n+; i++)

             for(j = ;j <= n+ ; j++)

                 w[i][j] = INF;

         for(i = ;i <= n+ ; i++)

             for(j = ; j <= n+ ; j++)

             {

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

                 if(w[i][j]==) w[i][j] = INF;

                 if(i==j) w[i][i] = ;

                 w[j][i] = w[i][j];

             }

         for(i =  ; i <= n+; i++)

             for(j = ; j <= n+ ;j++)

                 for(g = ;g <= n+; g++)

                 w[j][g] = min(w[j][g],w[j][i]+w[i][g]);

         st = ;

         en = n+;

         int low = ,high = ,mid;

         while(low<=high)

         {

             mid = (low+high)>>;

             memset(gh,,sizeof(gh));

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

             gh[i][en] = m;

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

             gh[st][i] = ;

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

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

                 if(w[i][j]<=mid)

                 gh[i][j] = w[i][j];

             //cout<<EK()<<endl;

             if(EK()==c)

             high = mid-;

             else

             low =mid+;

         }

         cout<<low<<endl;

     }

     return ;

 }