#include <bits/stdc++.h>
using namespace std;
struct edge {
  int b;
  int cap, f, cost;
  int rev_id;
};
vector<edge> E[55];
int dist[55];
int from[55], from_edge[55];
int res[55];
struct sf {
  bool operator()(const int& a, const int& b) const {
    return dist[a] > dist[b];
  }
};
int find_aug(int s, int t) {
  for (int i = (s); i <= (t); ++i) dist[i] = 2000005000, res[i] = 0;
  priority_queue<int, vector<int>, sf> Q;
  dist[s] = 0;
  res[s] = 2000005000;
  Q.push(s);
  while (!Q.empty()) {
    int i = Q.top();
    Q.pop();
    if (i == t) return res[t];
    int numE = E[i].size();
    for (int x = 0; x < (numE); ++x) {
      int j = E[i][x].b;
      int c = min(E[i][x].cap - E[i][x].f, res[i]);
      int newdist = dist[i] + E[i][x].cost;
      if (c && (newdist < dist[j])) {
        dist[j] = newdist;
        res[j] = c, from[j] = i, from_edge[j] = x;
        Q.push(j);
      }
    }
  }
  return res[t];
}
unsigned int min_cost_max_flow(int N, int K) {
  int ans = 0, flow = 0, tmp = 0, cst = 0;
  while ((tmp = find_aug(0, N - 1))) {
    if (dist[N - 1] > 0) tmp = min(tmp, 1);
    for (int j = N - 1, i = from[j]; j != 0; j = i, i = from[j]) {
      int x = from_edge[j];
      int y = E[i][x].rev_id;
      E[i][x].f += tmp;
      E[j][y].f -= tmp;
      assert(E[j][y].rev_id == x);
      assert(E[i][x].f <= E[i][x].cap);
      assert(E[j][y].f <= E[j][y].cap);
    }
    cst += tmp * dist[N - 1];
    flow += tmp;
    if (cst <= K)
      ans = max(ans, flow);
    else
      break;
  }
  return ans;
}
void add_edge(int a, int b, int cap, int cost) {
  edge x = {b, cap, 0, cost, (int)E[b].size()};
  edge y = {a, 0, 0, -cost, (int)E[a].size()};
  E[a].push_back(x);
  E[b].push_back(y);
}
int main() {
  int N, K, c;
  cin >> N >> K;
  for (int i = 0; i < (N); ++i)
    for (int j = 0; j < (N); ++j) {
      cin >> c;
      if (!c) continue;
      add_edge(i, j, c, 0);
      add_edge(i, j, K, 1);
    }
  int ans = min_cost_max_flow(N, K);
  cout << ans << endl;
}
