#include <bits/stdc++.h>
using namespace std;
struct EDGE {
  int to, next, w, co;
} e[100000];
int head[100], top, vis[100000];
void add(int u, int v, int w, int co) {
  e[top].to = v;
  e[top].w = w;
  e[top].co = co;
  e[top].next = head[u];
  head[u] = top++;
}
struct _ {
  int max_flow, co;
};
int dis[100], vvis[100], prep[100], pree[100];
queue<int> q;
deque<int> node;
void spfa(int s) {
  memset(dis, 63, sizeof(dis));
  memset(vvis, 0, sizeof(vvis));
  dis[s] = 0;
  q.push(s);
  int i;
  while (!q.empty()) {
    s = q.front();
    q.pop();
    vvis[s] = 0;
    int i;
    for (i = head[s]; ~i; i = e[i].next) {
      if (!e[i].w) continue;
      if (dis[s] + e[i].co < dis[e[i].to]) {
        dis[e[i].to] = dis[s] + e[i].co;
        pree[e[i].to] = i;
        prep[e[i].to] = s;
        if (vvis[e[i].to]) continue;
        vvis[e[i].to] = 1;
        q.push(e[i].to);
      }
    }
  }
}
_ dfs(int s, int t, int rest) {
  int flow = 998244353, co = 0;
  int temp = t;
  _ rv;
  while (t != s) {
    flow = min(flow, e[pree[t]].w);
    co += e[pree[t]].co;
    t = prep[t];
  }
  if (co > 0) flow = min(flow, rest / co);
  if (flow == 0) return rv = (_){0, 0};
  t = temp;
  while (t != s) {
    temp = pree[t];
    e[temp].w -= flow;
    e[temp ^ 1].w += flow;
    t = prep[t];
  }
  rv = (_){flow, co};
  return rv;
}
long long EK(int s, int t, int rest) {
  long long sum = 0;
  _ _;
  while (1) {
    spfa(s);
    if (dis[t] > 998244353) break;
    _ = dfs(s, t, rest);
    if (_.max_flow == 0) break;
    sum += _.max_flow;
    rest -= _.max_flow * _.co;
  }
  return sum;
}
int main() {
  memset(head, 255, sizeof(head));
  int n, k;
  scanf("%d%d", &n, &k);
  int i, j, t;
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      scanf("%d", &t);
      if (t) {
        add(i, j, t, 0);
        add(j, i, 0, 0);
        add(i, j, k, 1);
        add(j, i, 0, -1);
      }
    }
  }
  long long ans = EK(1, n, k);
  printf("%lld\n", ans);
  return 0;
}
