#include <bits/stdc++.h>
using namespace std;
int read(int &x) { return scanf("%d", &x); }
int read(int &x, int &y) { return scanf("%d%d", &x, &y); }
int read(int &x, int &y, int &z) { return scanf("%d%d%d", &x, &y, &z); }
int read(long long &x) { return scanf("%lld", &x); }
int read(long long &x, long long &y) { return scanf("%lld%lld", &x, &y); }
int read(double &x) { return scanf("%lf", &x); }
char buff[2000010];
int read(string &s) {
  int r = scanf("%s", buff);
  s = buff;
  return r;
}
const long long INF = 1000000000000000000LL;
struct Edge {
  int to, cap, cost, flow, back;
};
struct MinCostFlow {
  int n;
  vector<vector<Edge>> g;
  MinCostFlow(int n) : n(n), g(n) {}
  void add_rib(int a, int b, int u, int c) {
    Edge r1 = {b, u, c, 0, int(g[b].size())};
    Edge r2 = {a, 0, -c, 0, int(g[a].size())};
    g[a].push_back(r1);
    g[b].push_back(r2);
  }
  pair<long long, long long> run(int s, int t,
                                 long long k = 1000000000000000000LL,
                                 long long maxCost = 1000000000000000000LL) {
    long long flow = 0, cost = 0;
    while (flow < k) {
      vector<int> id(n, 0);
      vector<long long> d(n, INF);
      vector<int> q(n);
      vector<int> p(n);
      vector<size_t> p_rib(n);
      int qh = 0, qt = 0;
      q[qt++] = s;
      d[s] = 0;
      while (qh != qt) {
        int v = q[qh++];
        id[v] = 2;
        if (qh == n) qh = 0;
        for (int i = 0; i < g[v].size(); ++i) {
          Edge &r = g[v][i];
          if (r.flow < r.cap && d[v] + r.cost < d[r.to]) {
            d[r.to] = d[v] + r.cost;
            if (id[r.to] != 1) {
              q[qt++] = r.to;
              if (qt == n) qt = 0;
            }
            id[r.to] = 1;
            p[r.to] = v;
            p_rib[r.to] = i;
          }
        }
      }
      if (d[t] == INF) break;
      long long addflow = k - flow;
      long long addcost = 0;
      for (int v = t; v != s; v = p[v]) {
        Edge &f = g[p[v]][p_rib[v]];
        addflow = min(addflow, (long long)f.cap - f.flow);
        addcost += f.cost;
      }
      if (addcost > (maxCost - cost)) break;
      if (addcost > 0) addflow = min(addflow, (maxCost - cost) / addcost);
      if (addflow == 0) break;
      for (int v = t; v != s; v = p[v]) {
        Edge &f = g[p[v]][p_rib[v]];
        Edge &b = g[v][f.back];
        f.flow += addflow;
        b.flow -= addflow;
        cost += f.cost * addflow;
      }
      flow += addflow;
    }
    return make_pair(flow, cost);
  }
};
int main() {
  int TC = 1;
  while (TC-- > 0) {
    int N, K;
    read(N, K);
    MinCostFlow minCostFlow(N);
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        int c;
        read(c);
        if (c > 0) {
          minCostFlow.add_rib(i, j, c, 0);
          minCostFlow.add_rib(i, j, K, 1);
        }
      }
    }
    auto a = minCostFlow.run(0, N - 1, 1000000000000000000LL, K);
    cout << a.first << endl;
  }
}
