#include <bits/stdc++.h>
using namespace std;
const int maxn = 10000;
const int maxm = 100000;
const int inf = 0x3fffffff;
struct Edge {
  Edge(){};
  Edge(int a, int b, int c, int d) {
    to = a;
    cost = c;
    next = d;
    cap = b;
  };
  int to, cost, next, cap;
} edge[maxm];
int head[maxn], n, m, src, sink, tot;
void init() {
  tot = 0;
  memset(head, -1, sizeof(head));
}
void addedge(int u, int v, int cap, int cost) {
  edge[tot] = Edge(v, cap, cost, head[u]);
  head[u] = tot++;
  edge[tot] = Edge(u, 0, -cost, head[v]);
  head[v] = tot++;
}
int dis[maxn], pre[maxn], vis[maxn];
queue<int> q;
bool spfa() {
  int i, j;
  for (i = 1; i <= n; i++) dis[i] = inf, pre[i] = -1, vis[i] = 0;
  vis[src] = 1;
  dis[src] = 0;
  while (!q.empty()) q.pop();
  q.push(src);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    vis[u] = 0;
    for (i = head[u]; i != -1; i = edge[i].next) {
      int v = edge[i].to;
      if (edge[i].cap && dis[v] > dis[u] + edge[i].cost) {
        dis[v] = dis[u] + edge[i].cost;
        pre[v] = i;
        if (!vis[v]) {
          vis[v] = 1;
          q.push(v);
        }
      }
    }
  }
  if (pre[sink] == -1) return false;
  return true;
}
int k;
int mincostflow(int &cost) {
  int flow = 0;
  cost = 0;
  while (spfa()) {
    int Min = inf;
    for (int i = pre[sink]; i != -1; i = pre[edge[i ^ 1].to]) {
      if (Min > edge[i].cap) {
        Min = edge[i].cap;
      }
    }
    for (int i = pre[sink]; i != -1; i = pre[edge[i ^ 1].to]) {
      edge[i].cap -= Min;
      edge[i ^ 1].cap += Min;
    }
    int tmp = cost + Min * dis[sink];
    if (tmp > k) {
      flow += (k - cost) / (dis[sink]);
      return flow;
    }
    cost = tmp;
    flow += Min;
  }
  return flow;
}
int a[55][55];
int main() {
  int i, j;
  while (scanf("%d%d", &n, &k) != EOF) {
    init();
    for (i = 1; i <= n; i++) {
      for (j = 1; j <= n; j++) {
        scanf("%d", &a[i][j]);
        if (a[i][j]) {
          addedge(i, j, a[i][j], 0);
          addedge(i, j, k, 1);
        }
      }
    }
    src = 1;
    sink = n;
    int ans = 0;
    printf("%d\n", mincostflow(ans));
  }
}
