#include <bits/stdc++.h>
using namespace std;
const double EPS = -1e8;
const double Pi = acos(-1);
bool inline equ(double a, double b) { return fabs(a - b) < EPS; }
struct MinCostMaxFlow {
  static const int MAXV = 20010;
  static const int INF = 1000000000;
  struct Edge {
    int v, cap, w, rev;
    Edge() {}
    Edge(int t2, int t3, int t4, int t5) : v(t2), cap(t3), w(t4), rev(t5) {}
  };
  int V, s, t;
  vector<Edge> g[MAXV];
  void init(int n) {
    V = n + 2;
    s = n + 1, t = n + 2;
    for (int i = 1; i <= V; i++) g[i].clear();
  }
  void addEdge(int a, int b, int cap, int w) {
    g[a].push_back(Edge(b, cap, w, (int)g[b].size()));
    g[b].push_back(Edge(a, 0, -w, ((int)g[a].size()) - 1));
  }
  int d[MAXV], id[MAXV], mom[MAXV];
  bool inqu[MAXV];
  int qu[2000000], ql, qr;
  pair<int, int> mncmxf() {
    int mxf = 0, mnc = 0;
    while (1) {
      fill(d + 1, d + 1 + V, INF);
      fill(inqu + 1, inqu + 1 + V, 0);
      fill(mom + 1, mom + 1 + V, -1);
      mom[s] = s;
      d[s] = 0;
      ql = 1, qr = 0;
      qu[++qr] = s;
      inqu[s] = 1;
      while (ql <= qr) {
        int u = qu[ql++];
        inqu[u] = 0;
        for (int i = 0; i < (int)g[u].size(); i++) {
          Edge &e = g[u][i];
          int v = e.v;
          if (e.cap > 0 && d[v] > d[u] + e.w) {
            d[v] = d[u] + e.w;
            mom[v] = u;
            id[v] = i;
            if (!inqu[v]) qu[++qr] = v, inqu[v] = 1;
          }
        }
      }
      if (mom[t] == -1) break;
      int df = INF;
      for (int u = t; u != s; u = mom[u]) df = min(df, g[mom[u]][id[u]].cap);
      for (int u = t; u != s; u = mom[u]) {
        Edge &e = g[mom[u]][id[u]];
        e.cap -= df;
        g[e.v][e.rev].cap += df;
      }
      mxf += df;
      mnc += df * d[t];
    }
    return pair<int, int>(mnc, mxf);
  }
} flow;
const int MAXN = 55;
int n, k, c[MAXN][MAXN];
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n >> k;
  for (int i = (1); i <= (n); i++)
    for (int j = (1); j <= (n); j++) cin >> c[i][j];
  int lb = 0, ub = 100000000, ans = -1;
  while (lb <= ub) {
    int mid = (lb + ub) / 2;
    flow.init(n);
    for (int i = (1); i <= (n); i++)
      for (int j = (1); j <= (n); j++) {
        if (c[i][j]) {
          flow.addEdge(i, j, c[i][j], 0);
          flow.addEdge(i, j, k, 1);
        }
      }
    flow.addEdge(flow.s, 1, mid, 0);
    flow.addEdge(n, flow.t, mid, 0);
    pair<int, int> p = flow.mncmxf();
    if (p.first <= k) {
      ans = p.second;
      lb = mid + 1;
    } else
      ub = mid - 1;
  }
  cout << ans << endl;
}
