#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
template <class S, class T>
ostream& operator<<(ostream& os, const pair<S, T>& p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, const unordered_set<T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class S, class T>
ostream& operator<<(ostream& os, const unordered_map<S, T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, const multiset<T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class S, class T>
ostream& operator<<(ostream& os, const map<S, T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class T>
void dbs(string str, T t) {
  cerr << str << " : " << t << "\n";
}
template <class T, class... S>
void dbs(string str, T t, S... s) {
  long long idx = str.find(',');
  cerr << str.substr(0, idx) << " : " << t << ",";
  dbs(str.substr(idx + 1), s...);
}
template <class T>
void prc(T a, T b) {
  cerr << "[";
  for (T i = a; i != b; ++i) {
    if (i != a) cerr << ", ";
    cerr << *i;
  }
  cerr << "]\n";
}
long long power(long long x, long long y) {
  long long res = 1;
  while (y) {
    if (y & 1) res = (res * x) % 1000000007;
    y = y / 2, x = (x * x) % 1000000007;
  }
  return res % 1000000007;
}
const int INF = 0x3f3f3f3f;
struct edge {
  int u, v;
  int flow;
  int cost;
  edge() {}
  edge(int u, int v, int f, int c) : u(u), v(v), flow(f), cost(c) {}
};
struct MinCostMaxFlow {
  int N;
  vector<vector<int> > G;
  vector<edge> E;
  int numEdges;
  vector<int> found, dad;
  vector<int> dist;
  MinCostMaxFlow(int N) : N(N), G(N), numEdges(0), found(N), dad(N), dist(N) {}
  void addEdge(int from, int to, int capacity, int cost) {
    G[from].push_back(numEdges++);
    E.push_back(edge(from, to, capacity, cost));
    G[to].push_back(numEdges++);
    E.push_back(edge(to, from, 0, int(-1) * cost));
  }
  bool spfa(int s, int t) {
    fill(dad.begin(), dad.end(), -1);
    fill(dist.begin(), dist.end(), INF);
    fill(found.begin(), found.end(), 0);
    queue<int> Q;
    dist[s] = 0;
    Q.push(s);
    found[s] = true;
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      if (u == t) continue;
      for (int i = 0; i < (int)G[u].size(); ++i) {
        edge& pres = E[G[u][i]];
        int v = pres.v;
        if (pres.flow <= 0) continue;
        if (dist[u] + pres.cost < dist[v]) {
          dad[v] = G[u][i];
          dist[v] = dist[u] + pres.cost;
          if (!found[v]) Q.push(v), found[v] = true;
        }
      }
      found[u] = false;
    }
    return (dad[t] != -1);
  }
  int dfs(int t) {
    int flow = INF;
    for (int i = dad[t]; i != -1; i = dad[E[i].u]) {
      if (E[i].flow < flow) flow = E[i].flow;
    }
    for (int i = dad[t]; i != -1; i = dad[E[i].u]) {
      E[i].flow -= flow;
      E[i ^ 1].flow += flow;
    }
    return flow;
  }
  pair<int, int> getMaxFlow(int s, int t) {
    int totflow = 0;
    int totcost = 0;
    while (spfa(s, t)) {
      int amt = dfs(t);
      totflow += amt;
      totcost += dist[t] * (int)amt;
    }
    return make_pair(totflow, totcost);
  }
};
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long n, k;
  cin >> n >> k;
  long long cost[n + 1][n + 1];
  long long i, j;
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      cin >> cost[i][j];
    }
  }
  long long low = 0, high = 1e9;
  long long ans = 0;
  while (low <= high) {
    long long mid = (low + high) / 2;
    long long source = 0, sink = n + 1;
    MinCostMaxFlow df(sink + 1);
    df.addEdge(source, 1, mid, 0);
    df.addEdge(n, sink, mid, 0);
    for (i = 1; i <= n; i++) {
      for (j = 1; j <= n; j++) {
        if (cost[i][j]) {
          df.addEdge(i, j, cost[i][j], 0);
          df.addEdge(i, j, k, 1);
        }
      }
    }
    pair<long long, long long> lol = df.getMaxFlow(source, sink);
    if (lol.first == mid and lol.second <= k)
      ans = mid, low = mid + 1;
    else
      high = mid - 1;
  }
  cout << ans;
}
