#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

#define maxn	300
#define inf		1000000

int s, t;
int k, c, m, n;
int map[maxn][maxn], dist[maxn], num[maxn], pre[maxn], now[maxn];
int dis[maxn][maxn];

void initialize()
{
	s = 0;
	n = k + c;
	t = n + 1;
	memset(dis, 0, sizeof(dis));
}

void floyd()
{
	int i, j, v;
	for (i=1; i<=n; i++)
	{
		for (j=1; j<=n; j++)
		{
			for (v=1; v<=n; v++)
			{
				if (dis[j][v] > dis[j][i] + dis[i][v])
				{
					dis[j][v] = dis[j][i] + dis[i][v];
				}
			}
		}
	}
}

void init(int mid)
{
	int i, j;
	memset(map, 0, sizeof(map));
	memset(num, 0, sizeof(num));
	memset(now, 0, sizeof(now));
	memset(pre, 0, sizeof(pre));
	for (i=k+1; i<=n; i++)
	{
		map[s][i] = 1;
	}
	for (i=1; i<=k; i++)
	{
		map[i][t] = m;
	}
	for (i=k+1; i<=n; i++)
	{
		for (j=1; j<=k; j++)
		{
			if (mid >= dis[i][j])
			{
				map[i][j] = 1;
			}
		}
	}
}

void bfs()
{
	int i;
	for (i=s; i<=t; i++)
	{
		dist[i] = t+1;
	}
	dist[t] = 0;
	num[0]++;

	queue<int> q;
	q.push(t);
	while (!q.empty())
	{
		int u = q.front();
		q.pop();

		for (i=s; i<=t; i++)
		{
			if (dist[i] > t && map[i][u])
			{
				dist[i] = dist[u] + 1;
				num[dist[i]]++;
				q.push(i);
			}
		}
	}
}

int augment()
{
	int tmp, width = (0x7ffffff);
	int i;
	for (i=t; i != s; i=pre[i])
	{
		tmp = map[pre[i]][i];
		if (tmp < width)
		{
			width = tmp;
		}
	}
	for (i=t; i != s; i=pre[i])
	{
		map[i][pre[i]] += width;
		map[pre[i]][i] -= width;
	}
	return width;
}

int retreat(int &i)
{
	int tmp, j;
	int mind = t;
	for (j=s; j<=t; j++)
	{
		if (map[i][j] && dist[j] < mind)
		{
			mind = dist[j];
		}
	}
	tmp = dist[i];
	num[tmp]--;
	dist[i] = mind + 1;
	num[dist[i]]++;
	if (i != s)
	{
		i = pre[i];
	}
	return num[tmp];
}

int isap()
{
	int f = 0;
	int i, j;
	bfs();
/*
	for (i=s; i<=t; i++)
	{
		now[i] = s;
	}
*/
	i = s;
	while (dist[s] < t+1)
	{
		for (j = now[i]; j<=t; j++)
		{
			if (map[i][j] && dist[i] == dist[j]+1)
			{
				break;
			}
		}
		if (j <= t)
		{
			now[i] = j;
			pre[j] = i;
			i = j;
			if (i == t)
			{
				f += augment();
				i = s;
			}
		}
		else
		{
			now[i] = s;
			if (retreat(i) == 0)
			{
				break;
			}
		}
	}
	return f;
}

int main()
{
	while (scanf("%d %d %d", &k, &c, &m) != EOF)
	{
		int i, j;
		initialize();
		for (i=1; i<=n; i++)
		{
			for (j=1; j<=n; j++)
			{
				scanf("%d", &dis[i][j]);
				if (!dis[i][j])
				{
					dis[i][j] = inf;
				}
			}
		}
		floyd();
		int low = 0, high = 20000, mid;
		mid = (low + high) / 2;
		while (low < high)
		{
			init(mid);
			if (isap() >= c)
			{
				high = mid - 1;
			}
			else
			{
				low = mid + 1;
			}
			mid = (low + high)/2;
		}
		printf("%d\n", mid);
	}
	return 0;
}