#include <bits/stdc++.h>
using namespace std;
bool debug;
const int inf = 1e9 + 5;
const int nax = 205;
int k;
namespace MinCost {
struct Edge {
  int w, c, v, rev;
  Edge(int _w, int _c, int _v, int _rev) : w(_w), c(_c), v(_v), rev(_rev) {}
};
int odl[nax], pot[nax], pop[nax], pop_kraw[nax];
vector<Edge> v[nax];
bool bylo[nax];
void init(int n) {
  for (int i = 0; i <= n; ++i) v[i].clear();
}
void AddEdge(int a, int b, int cap, int cost) {
  v[a].push_back(Edge(b, cap, cost, int(v[b].size()) + (a == b)));
  v[b].push_back(Edge(a, 0, -cost, int(v[a].size() - 1)));
}
pair<int, int> MinCostMaxFlow(int s, int t, int n) {
  int flow = 0, cost = 0;
  for (int i = 0; i <= n; ++i) pot[i] = 0;
  while (true) {
    for (int i = 0; i <= n; ++i) {
      odl[i] = inf;
      bylo[i] = false;
    }
    odl[s] = 0;
    for (int k = 0; k <= (n)-1; ++k) {
      int x = 0;
      int najm = inf;
      for (int i = 0; i <= n; ++i)
        if (!bylo[i] && najm > odl[i]) {
          x = i;
          najm = odl[i];
        }
      bylo[x] = true;
      int dl = v[x].size();
      for (int i = 0; i <= (dl)-1; ++i)
        if (v[x][i].c > 0 &&
            odl[v[x][i].w] > odl[x] + pot[x] - pot[v[x][i].w] + v[x][i].v) {
          odl[v[x][i].w] = odl[x] + pot[x] - pot[v[x][i].w] + v[x][i].v;
          pop[v[x][i].w] = x;
          pop_kraw[v[x][i].w] = i;
        }
    }
    if (odl[t] == inf) break;
    for (int i = 0; i <= n; ++i) pot[i] += odl[i];
    int x = t;
    int cap = inf;
    while (x != s) {
      cap = min(cap, v[pop[x]][pop_kraw[x]].c);
      x = pop[x];
    }
    x = t;
    int one_path_cost = 0;
    while (x != s) {
      one_path_cost += v[pop[x]][pop_kraw[x]].v;
      v[pop[x]][pop_kraw[x]].c -= cap;
      v[x][v[pop[x]][pop_kraw[x]].rev].c += cap;
      x = pop[x];
    }
    int ile_zmiesci = one_path_cost ? (k - cost) / one_path_cost : inf;
    cost += min(cap, ile_zmiesci) * one_path_cost;
    flow += min(cap, ile_zmiesci);
    if (ile_zmiesci < cap) break;
  }
  return make_pair(flow, cost);
}
};  // namespace MinCost
using namespace MinCost;
int n, a;
int main(int argc, char* argv[]) {
  scanf("%d%d", &n, &k);
  init(n - 1);
  for (int i = 0; i <= (n)-1; ++i)
    for (int j = 0; j <= (n)-1; ++j) {
      scanf("%d", &a);
      if (a > 0) {
        AddEdge(i, j, a, 0);
        AddEdge(i, j, k, 1);
      }
    }
  printf("%d\n", MinCostMaxFlow(0, n - 1, n - 1).first);
  return 0;
}
