const int MAXN = 240;

struct Edge
{
    int from, to, cap, flow;
    bool operator< (const Edge& rhs) const
    {
        return from < rhs.from || (from == rhs.from && to < rhs.to);
    }
};

const int MAXV = MAXN;
struct ISAP
{
    int n, m, s, t;
    vector<Edge> edges;
    vector<int> G[MAXV];   // 邻接表，G[i][j]表示结点i的第j条边在e数组中的序号
    bool vis[MAXV];        // BFS使用
    int d[MAXV];           // 从起点到i的距离
    int cur[MAXV];        // 当前弧指针
    int p[MAXV];          // 可增广路上的上一条弧
    int num[MAXV];        // 距离标号计数

    void AddEdge(int from, int to, int cap)
    {
        edges.push_back((Edge) { from, to, cap, 0 });
        edges.push_back((Edge) { to, from, 0, 0 });
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool BFS()
    {
        memset(vis, 0, sizeof(vis));
        queue<int> Q;
        Q.push(t);
        vis[t] = 1;
        d[t] = 0;
        while(!Q.empty())
        {
            int x = Q.front();
            Q.pop();
            REP(i, G[x].size())
            {
                Edge& e = edges[G[x][i]^1];
                if(!vis[e.from] && e.cap > e.flow)
                {
                    vis[e.from] = 1;
                    d[e.from] = d[x] + 1;
                    Q.push(e.from);
                }
            }
        }
        return vis[s];
    }

    void ClearAll(int n)
    {
        this->n = n;
        REP(i, n)
            G[i].clear();
        edges.clear();
    }

    void ClearFlow()
    {
        REP(i, edges.size())
            edges[i].flow = 0;
    }

    int Augment()
    {
        int x = t, a = INF;
        while(x != s)
        {
            Edge& e = edges[p[x]];
            a = min(a, e.cap-e.flow);
            x = edges[p[x]].from;
        }
        x = t;
        while(x != s)
        {
            edges[p[x]].flow += a;
            edges[p[x]^1].flow -= a;
            x = edges[p[x]].from;
        }
        return a;
    }

    int Maxflow(int s, int t, int need)
    {
        this->s = s;
        this->t = t;
        int flow = 0;
        BFS();
        memset(num, 0, sizeof(num));
        REP(i, n) num[d[i]]++;
        int x = s;
        memset(cur, 0, sizeof(cur));
        while(d[s] < n)
        {
            if(x == t)
            {
                flow += Augment();
                if(flow >= need) return flow;
                x = s;
            }
            int ok = 0;
            FF(i, cur[x], G[x].size())
            {
                Edge& e = edges[G[x][i]];
                if(e.cap > e.flow && d[x] == d[e.to] + 1)   // Advance
                {
                    ok = 1;
                    p[e.to] = G[x][i];
                    cur[x] = i; // 注意
                    x = e.to;
                    break;
                }
            }
            if(!ok)   // Retreat
            {
                int m = n-1; // 初值注意
                REP(i, G[x].size())
                {
                    Edge& e = edges[G[x][i]];
                    if(e.cap > e.flow)
                        m = min(m, d[e.to]);
                }
                if(--num[d[x]] == 0)
                    break;
                num[d[x] = m + 1]++;
                cur[x] = 0; // 注意
                if(x != s)
                    x = edges[p[x]].from;
            }
        }
        return flow;
    }

    vector<int> Mincut()   // call this after maxflow
    {
        BFS();
        vector<int> ans;
        REP(i, edges.size())
        {
            Edge& e = edges[i];
            if(!vis[e.from] && vis[e.to] && e.cap > 0)
                ans.push_back(i);
        }
        return ans;
    }

    void Reduce()
    {
        REP(i, edges.size())
            edges[i].cap -= edges[i].flow;
    }

    void print()
    {
        printf("Graph:\n");
        REP(i, edges.size())
            printf("%d->%d, %d, %d\n", edges[i].from, edges[i].to , edges[i].cap, edges[i].flow);
    }
} mf;

int dist[MAXN][MAXN];
int n, m, k;
//machine cow maxnumber

bool check(int Max)
{
    mf.ClearAll(n + m + 2);
    int S = 0, T = n + m + 1;
    FE(i, 1, n)
        mf.AddEdge(i, T, k);
    FE(i, n + 1, n + m)
        mf.AddEdge(S, i, 1);
    FE(i, n + 1, n + m) FE(j, 1, n)
        if (dist[i][j] <= Max)
            mf.AddEdge(i, j, 1);
    return mf.Maxflow(S, T, INF) == m;
}

int main()
{
    while (~RIII(n, m, k))
    {
        FE(i, 1, n + m) FE(j, 1, n + m)
        {
            RI(dist[i][j]);
            if (dist[i][j] == 0)
                dist[i][j] = INF;
        }
        FE(k, 1, n + m) FE(i, 1, n + m) FE(j, 1, n + m)
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        int l = 0, r = INF;
        while (l <= r)
        {
            int m = (l + r) >> 1;
            if (check(m))
                r = m - 1;
            else
                l = m + 1;
        }
        WI(l);
    }
    return 0;
}