#include <bits/stdc++.h>
using namespace std;
const int MAX = 105;
const int INF = 1e9;
int c[MAX][MAX];
template <int SZ>
struct MCMF {
  int N = 0, s, t;
  struct Edge {
    int to, rev;
    int flow, cap;
    long long cost;
    int id;
  };
  vector<Edge> adj[SZ];
  void addEdge(int u, int v, int cap, long long cost, int id = 0) {
    N = max(N, max(u, v) + 1);
    Edge a = {v, (int)adj[v].size(), 0, cap, cost, id},
         b = {u, (int)adj[u].size(), 0, 0, -cost, 0};
    adj[u].push_back(a), adj[v].push_back(b);
  }
  pair<int, int> pre[SZ];
  pair<long long, int> cost[SZ];
  long long totCost = 0, curCost = 0;
  int totFlow = 0;
  bool SPFA() {
    for (int i = 0; i < SZ; i++)
      cost[i] = {numeric_limits<long long>::max(), 0};
    cost[s] = {0, numeric_limits<int>::max()};
    priority_queue<pair<long long, int>, vector<pair<long long, int>>,
                   greater<pair<long long, int>>>
        pq;
    pq.push({0, s});
    while (!pq.empty()) {
      pair<long long, int> cur = pq.top();
      pq.pop();
      if (cur.first > cost[cur.second].first) continue;
      for (auto &e : adj[cur.second]) {
        if (e.flow == e.cap) continue;
        if (cost[e.to].first > cur.first + e.cost) {
          cost[e.to] = {cur.first + e.cost,
                        min(e.cap - e.flow, cost[cur.second].second)};
          pre[e.to] = {cur.second, e.rev};
          pq.push({cost[e.to].first, e.to});
        }
      }
    }
    return cost[t].second;
  }
  void backTrack() {
    int df = cost[t].second;
    totFlow += df;
    curCost += cost[t].first;
    totCost += curCost * df;
    for (int u = t; u != s; u = pre[u].first) {
      adj[u][pre[u].second].flow -= df;
      adj[pre[u].first][adj[u][pre[u].second].rev].flow += df;
    }
    for (int i = 0; i < SZ; i++)
      for (auto &e : adj[i]) e.cost += cost[i].first - cost[e.to].first;
  }
  pair<int, long long> calc(int _s, int _t) {
    s = _s, t = _t;
    while (SPFA()) backTrack();
    return {totFlow, totCost};
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) cin >> c[i][j];
  int l = 0, r = INF;
  while (r - l > 1) {
    int m = (l + r) / 2;
    MCMF<MAX> Network;
    int s = 0, t = n;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (c[i][j]) {
          Network.addEdge(i, j, c[i][j], 0);
          Network.addEdge(i, j, INF, 1);
        }
      }
    }
    Network.addEdge(s, 1, m, 0);
    auto p = Network.calc(s, t);
    if (p.second <= k && p.first == m)
      l = m;
    else
      r = m;
  }
  cout << l;
  return 0;
}
