#include <bits/stdc++.h>
using namespace std;
int n, k, cnt;
int head[60], dis[60], pre[60], vis[60];
int ans;
struct Edge {
  int u, v, c, w, next;
} edge[50 * 50 * 2 * 2];
void init() {
  memset(head, -1, sizeof(head));
  cnt = 0;
}
void addedge(int u, int v, int cap, int cost) {
  edge[cnt].u = u;
  edge[cnt].v = v;
  edge[cnt].c = cap;
  edge[cnt].w = cost;
  edge[cnt].next = head[u];
  head[u] = cnt++;
  edge[cnt].u = v;
  edge[cnt].v = u;
  edge[cnt].c = 0;
  edge[cnt].w = -cost;
  edge[cnt].next = head[v];
  head[v] = cnt++;
}
bool spfa() {
  int i, j;
  queue<int> q;
  q.push(0);
  for (int i = 1; i <= n; i++) {
    dis[i] = 50 * 10000000;
    vis[i] = 0;
  }
  dis[0] = 0, vis[0] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    vis[u] = 0;
    for (int i = head[u]; i != -1; i = edge[i].next) {
      int v = edge[i].v;
      if (edge[i].c && dis[v] > dis[u] + edge[i].w) {
        dis[v] = dis[u] + edge[i].w;
        pre[v] = i;
        if (!vis[v]) {
          vis[v] = 1;
          q.push(v);
        }
      }
    }
  }
  if (dis[n] == 50 * 10000000) return 0;
  return 1;
}
bool end() {
  int u, p, cap = -1;
  for (u = n; u; u = edge[p].u) {
    p = pre[u];
    if (cap == -1 || cap > edge[p].c) cap = edge[p].c;
  }
  int tmp = 0;
  for (u = n; u; u = edge[p].u) {
    p = pre[u];
    tmp += edge[p].w;
  }
  if (k >= tmp * cap) {
    ans += cap, k -= tmp * cap;
    for (u = n; u; u = edge[p].u) {
      p = pre[u];
      edge[p].c -= cap;
      edge[p ^ 1].c += cap;
    }
    return 1;
  } else {
    ans += k / tmp, k %= tmp;
    return 0;
  }
}
int main() {
  init();
  ans = 0;
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      int tmp;
      scanf("%d", &tmp);
      if (tmp != 0) addedge(i, j, tmp, 0), addedge(i, j, 50 * 10000000, 1);
    }
  n--;
  while (spfa()) {
    bool tmp = end();
    if (!tmp) break;
  }
  printf("%d\n", ans);
  return 0;
}
