#include <bits/stdc++.h>
using namespace std;
int k, n, m, s, t, max_flow, check, notp;
vector<int> help[100500];
vector<int> bfs(vector<vector<int> > C) {
  vector<int> pred(n, 0);
  vector<int> mark(n, 0);
  queue<int> Q;
  mark[0] = 1;
  pred[0] = 0;
  Q.push(0);
  check = 0;
  while (!Q.empty() && mark[n - 1] == 0) {
    int u = Q.front();
    Q.pop();
    for (int v = 0; v < n; ++v) {
      if (mark[v] != 1 && C[u][v] > 0) {
        mark[v] = 1;
        pred[v] = u;
        Q.push(v);
      }
    }
    if (Q.empty()) {
      check = 1;
    }
  }
  if (mark[n - 1] == 0) check = 1;
  return pred;
}
void f_max_flow(vector<vector<int> > C) {
  max_flow = 0;
  vector<int> pred_p = bfs(C);
  if (notp == 1) return;
  while (check != 1) {
    vector<int> pred = bfs(C);
    int u = n - 1;
    int v = pred[u];
    int min_val = C[v][u];
    while (v > 0) {
      u = v;
      v = pred[v];
      if (min_val > C[v][u] && C[v][u] != 0) {
        min_val = C[v][u];
      }
    }
    u = n - 1;
    v = pred[u];
    C[v][u] -= min_val;
    while (v > 0) {
      u = v;
      v = pred[v];
      C[v][u] -= min_val;
      C[u][v] += min_val;
    }
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) help[i][j] -= C[i][j];
  }
  return;
}
vector<int> Dejkstra(vector<vector<int> > C) {
  int inf = 10050000;
  vector<int> d(n, inf);
  vector<int> p(n, -1);
  vector<int> way;
  p[0] = 0;
  d[0] = 0;
  int **matrix = new int *[n];
  for (int i = 0; i < n; ++i) matrix[i] = new int[n];
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) {
      if (C[i][j] > 0) {
        if (help[i][j] == C[i][j])
          matrix[i][j] = 1;
        else
          matrix[i][j] = 0;
      } else
        matrix[i][j] = inf;
    }
  queue<int> Q;
  Q.push(0);
  vector<int> mark_d(n, 0);
  while (!Q.empty()) {
    int v = Q.front();
    Q.pop();
    mark_d[v] = 1;
    for (int u = 0; u < n; ++u) {
      if (matrix[v][u] != inf) {
        if (d[u] > d[v] + matrix[v][u]) {
          d[u] = d[v] + matrix[v][u];
          p[u] = v;
          Q.push(u);
          mark_d[u] = 1;
        }
      }
    }
  }
  int top = n - 1;
  way.push_back(top);
  while (top != 0) {
    way.push_back(p[top]);
    top = p[top];
  }
  reverse(way.begin(), way.end());
  for (int i = 0; i < way.size() - 1; ++i) {
    if (help[way[i]][way[i + 1]] != C[way[i]][way[i + 1]]) {
      help[way[i]][way[i + 1]] += 1;
    }
  }
  return d;
}
int main() {
  cin >> n >> k;
  int x;
  vector<vector<int> > C(n, vector<int>(n));
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) {
      cin >> C[i][j];
      help[i].push_back(C[i][j]);
    }
  int s = 0;
  t = n - 1;
  f_max_flow(C);
  for (int i = 0; i < n; ++i) {
    max_flow += help[0][i];
  }
  if (max_flow != 0) {
    while (k > 0) {
      vector<int> d = Dejkstra(C);
      if (d[t] > k) break;
      k -= d[t];
      ++max_flow;
    }
  }
  cout << max_flow << endl;
  return 0;
}
