#include <bits/stdc++.h>
using namespace std;
int n, k, ans;
int head[52], pre[52], dis[52];
bool inq[52];
struct eed {
  int next, from, to, cow, cost;
} edge[52 * 52 * 8];
int ecnt;
queue<int> Q;
void addedge(int u, int v, int cow, int cost) {
  edge[ecnt].next = head[u];
  edge[ecnt].to = v;
  edge[ecnt].from = u;
  edge[ecnt].cow = cow;
  edge[ecnt].cost = cost;
  head[u] = ecnt++;
  edge[ecnt].next = head[v];
  edge[ecnt].to = u;
  edge[ecnt].from = v;
  edge[ecnt].cow = 0;
  edge[ecnt].cost = -cost;
  head[v] = ecnt++;
}
bool spfa() {
  memset(inq, 0, sizeof(inq));
  while (!Q.empty()) Q.pop();
  memset(dis, 0x3f, sizeof(dis));
  dis[1] = 0;
  Q.push(1);
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    for (int e = head[u]; ~e; e = edge[e].next) {
      int v = edge[e].to;
      if (edge[e].cow > 0 && dis[v] > dis[u] + edge[e].cost) {
        pre[v] = e;
        dis[v] = dis[u] + edge[e].cost;
        if (!inq[v]) {
          inq[v] = 1;
          Q.push(v);
        }
      }
    }
    inq[u] = 0;
  }
  if (dis[n] == 0x3f3f3f3f) return false;
  int flow = 0x3f3f3f3f;
  for (int u = n; u != 1; u = edge[pre[u]].from)
    flow = min(flow, edge[pre[u]].cow);
  if (!dis[n])
    ans += flow;
  else {
    if (dis[n] * flow >= k) {
      ans += k / dis[n];
      return false;
    } else {
      ans += flow;
      k -= flow * dis[n];
    }
  }
  for (int u = n; u != 1; u = edge[pre[u]].from) {
    edge[pre[u]].cow -= flow;
    edge[pre[u] ^ 1].cow += flow;
  }
  return true;
}
int main() {
  scanf("%d%d", &n, &k);
  int i, j;
  memset(head, -1, sizeof(head));
  ecnt = 0;
  for (i = 1; i <= n; ++i)
    for (j = 1; j <= n; ++j) {
      int c;
      scanf("%d", &c);
      if (c) {
        addedge(i, j, c, 0);
        addedge(i, j, 2000, 1);
      }
    }
  ans = 0;
  while (spfa())
    ;
  printf("%d\n", ans);
  return 0;
}
