#include <bits/stdc++.h>
using namespace std;
const int NMAX = 60, EMAX = 11000, INF = ~0u >> 1;
struct Edge {
  int y;
  int cost;
  int flow;
  int anti;
  int next;
};
int N, K;
int S, T, V[NMAX], edgeId;
Edge E[EMAX];
int dis[NMAX];
bool visit[NMAX];
deque<int> Q;
void insert(int x, int y, int cost, int flow) {
  E[++edgeId] = (Edge){y, cost, flow, 0, V[x]};
  V[x] = edgeId;
  E[++edgeId] = (Edge){x, -cost, 0, 0, V[y]};
  V[y] = edgeId;
  E[V[y]].anti = V[x];
  E[V[x]].anti = V[y];
}
bool SPFA() {
  int i, x;
  bool in[NMAX] = {};
  memset(dis, 0, sizeof(dis));
  memset(visit, 0, sizeof(visit));
  visit[S] = true;
  in[S] = true;
  Q.push_back(S);
  while (!Q.empty()) {
    x = Q.front();
    Q.pop_front();
    in[x] = false;
    for (i = V[x]; i > 0; i = E[i].next) {
      if (E[i].flow && (!visit[E[i].y] || dis[E[i].y] > dis[x] + E[i].cost)) {
        dis[E[i].y] = dis[x] + E[i].cost;
        visit[E[i].y] = true;
        if (!in[E[i].y]) {
          in[E[i].y] = true;
          Q.push_back(E[i].y);
        }
      }
    }
  }
  return visit[T];
}
int editEdge(int id, int flow) {
  E[id].flow -= flow;
  E[E[id].anti].flow += flow;
  return flow;
}
int DFS(int x, int can, int &cost, int &flow) {
  int i, tmp = 0;
  visit[x] = true;
  if (x == T) {
    int tmp = min(dis[T] ? ((K - cost) / dis[T]) : INF, can);
    flow += tmp;
    cost += tmp * dis[T];
    visit[x] = false;
    return can;
  }
  for (i = V[x]; i > 0 && tmp < can && (dis[T] ? ((K - cost) / dis[T]) : INF);
       i = E[i].next) {
    if (!visit[E[i].y] && E[i].flow && dis[E[i].y] == dis[x] + E[i].cost)
      tmp += editEdge(i, DFS(E[i].y, min(can - tmp, E[i].flow), cost, flow));
  }
  return tmp;
}
int minimumCostFlow() {
  int cost = 0, flow = 0;
  while (SPFA() && cost + dis[T] <= K) {
    memset(visit, 0, sizeof(visit));
    DFS(S, INF, cost, flow);
  }
  return flow;
}
int main() {
  int i, j, tmp;
  scanf("%d %d", &N, &K);
  S = 1;
  T = N;
  for (i = 1; i <= N; i += 1) {
    for (j = 1; j <= N; j += 1) {
      scanf("%d", &tmp);
      if (tmp) {
        insert(i, j, 0, tmp);
        insert(i, j, 1, INF);
      }
    }
  }
  printf("%d\n", minimumCostFlow());
  exit(0);
}
