#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50 + 10;
int n, k, c[MAXN][MAXN], g[MAXN][MAXN], dis[MAXN], head, tail, que[MAXN * 10],
    Tohka, pre[MAXN];
bool vis[MAXN];
bool BFS(int S, int T) {
  memset(vis, 0, sizeof(vis));
  pre[S] = 0, vis[S] = 1;
  head = 0, tail = 1, que[1] = S;
  while (head < tail) {
    int first = que[++head];
    for (int i = 1; i <= n; ++i)
      if (g[first][i] > 0 && !vis[i]) {
        vis[i] = true, pre[i] = first;
        que[++tail] = i;
        if (i == T) return true;
      }
  }
  return false;
}
int work(int S, int T) {
  int minf = 0x3f3f3f3f;
  for (int i = T; i != S; i = pre[i]) minf = min(g[pre[i]][i], minf);
  Tohka += minf;
  for (int i = T; i != S; i = pre[i])
    g[pre[i]][i] -= minf, g[i][pre[i]] += minf;
  return minf;
}
void SPFA(int S, int T) {
  memset(dis, 0x3f, sizeof(dis));
  memset(vis, 0, sizeof(vis));
  vis[S] = 1, dis[S] = 0;
  pre[S] = 0;
  head = 0, tail = 1, que[1] = S;
  while (head < tail) {
    int first = que[++head];
    vis[first] = false;
    for (int i = 1; i <= n; ++i)
      if (c[first][i] > 0 && dis[i] > dis[first] + (g[first][i] == 0)) {
        dis[i] = dis[first] + (g[first][i] == 0);
        pre[i] = first;
        if (!vis[i]) que[++tail] = i, vis[i] = 1;
      }
  }
}
int solve(int S, int T) {
  while (1) {
    while (BFS(S, T)) work(S, T);
    SPFA(S, T);
    if (dis[T] > k) break;
    for (int i = T; i != S; i = pre[i])
      if (g[pre[i]][i] == 0) ++g[pre[i]][i], --k;
  }
  return Tohka;
}
int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) cin >> c[i][j];
  memcpy(g, c, sizeof(c));
  cout << solve(1, n) << endl;
  fclose(stdin);
  fclose(stdout);
  return 0;
}
