/*      最大流SAP      邻接表      思路：基本源于FF方法，给每个顶点设定层次标号，和允许弧。      优化:      1、当前弧优化（重要）。      1、每找到以条增广路回退到断点（常数优化）。      2、层次出现断层，无法得到新流（重要）。      时间复杂度（m*n^2）*/#include <iostream>#include <cstdio>#include <cstring>#define ms(a,b) memset(a,b,sizeof a)using namespace std;const int INF = 300;int G[INF][INF];struct node {    int v, c, next;} edge[INF*INF*4];int  pHead[INF*INF], SS, ST, nCnt;//同时添加弧和反向边, 反向边初始容量为0void addEdge (int u, int v, int c) {    edge[++nCnt].v = v; edge[nCnt].c = c, edge[nCnt].next = pHead[u]; pHead[u] = nCnt;    edge[++nCnt].v = u; edge[nCnt].c = 0, edge[nCnt].next = pHead[v]; pHead[v] = nCnt;}int SAP (int pStart, int pEnd, int N) {    //层次点的数量  点的层次   点if(G[i][j]<l) l=G[i][j];的允许弧     当前走过边的栈    int numh[INF], h[INF], curEdge[INF], pre[INF];    //当前找到的流, 累计的流量, 当前点, 断点, 中间变量    int cur_flow, flow_ans = 0, u, neck, i, tmp;    //清空层次数组,    ms (h, 0); ms (numh, 0); ms (pre, -1);    //将允许弧设为邻接表的任意if(G[i][j]<l) l=G[i][j];一条边    for (i = 0; i <= N; i++) curEdge[i] = pHead[i];    numh[0] = N;//初始全部点的层次为0    u = pStart;//从源点开始    //如果从源点能找到增广路    while (h[pStart] <= N) {        //找到增广路        if (u == pEnd) {            cur_flow = 1e9;            //找到当前增广路中的最大流量, 更新断点            for (i = pStart; i != pEnd; i = edge[curEdge[i]].v)                if (cur_flow > edge[curEdge[i]].c) neck = i, cur_flow = edge[curEdge[i]].c;            //增加反向边的容量            for (i = pStart; i != pEnd; i = edge[curEdge[i]].v) {                tmp = curEdge[i];                edge[tmp].c -= cur_flow, edge[tmp ^ 1].c += cur_flow;            }            flow_ans += cur_flow;//累计流量            u = neck;//从断点开始找新的增广路        }        //找到一条允许弧        for ( i = curEdge[u]; i != 0; i = edge[i].next)            if (edge[i].c && h[u] == h[edge[i].v] + 1)     break;        //继续DFS        if (i != 0) {            curEdge[u] = i, pre[edge[i].v] = u;            u = edge[i].v;        }        //当前起点没有允许弧,从u找不到增广路        else {            //u所在的层次点减少一,且如果没有与当前点一个层次的点, 退出.            if (0 == --numh[h[u]]) continue;            //有与u相同层次的点, 更新u的层次 ,回到上一个点            curEdge[u] = pHead[u];            for (tmp = N, i = pHead[u]; i != 0; i = edge[i].next)                if (edge[i].c)  tmp = min (tmp, h[edge[i].v]);            h[u] = tmp + 1;            ++numh[h[u]];            if (u != pStart) u = pre[u];        }    }    return flow_ans;}int k, c, m, n;bool check (int tem) {    nCnt = 1;    SS = n + 1, ST = n + 2;    memset (pHead, 0, sizeof pHead);    for (int i = 1; i <= k; i++) {        addEdge (i, ST, m);        for (int j = k + 1; j <= k + c; j++)            if (G[j][i] <= tem)                addEdge (j, i, 1);    }    for (int i = k + 1; i <= k + c; i++) addEdge (SS, i, 1);    int ans = SAP (SS, ST, ST);    if (ans == c) return 1;    return 0;}int main() {    /*           建图,前向星存边，表头在pHead[],边计数 nCnt.           SS,ST分别为源点和汇点    */    scanf ("%d %d %d", &k, &c, &m);    n = k + c;    int l = 0, r = 10000;    for (int i = 1; i <= n; i++)        for (int j = 1; j <= n; j++) {            scanf ("%d", &G[i][j]);            if (G[i][j]==0)                G[i][j] = 0x3f3f3f;        }    for (int  t = 1; t <= n; t++) {        for (int i = 1; i <= n; i++)            for (int j = 1; j <= n; j++)                if (G[i][j] > G[i][t] + G[t][j]) G[i][j] = G[i][t] + G[t][j];    }    int last = -1;    while (l <= r) {        int mid = (l + r) >> 1;        if (check (mid) ) {            last = mid;            r = mid - 1;        }        else l = mid + 1;    }    printf ("%d", last);    return 0;}