#include <bits/stdc++.h>
using namespace std;
int Ans, Cap[55][55], From[55], K, N, T[55];
vector<int> E[55];
bool dijkstra() {
  priority_queue<pair<int, int>, vector<pair<int, int>>,
                 greater<pair<int, int>>>
      q;
  vector<int> d(55, 1005);
  d[1] = 0;
  q.push(make_pair(0, 1));
  while (!q.empty()) {
    pair<int, int> p = q.top();
    q.pop();
    int n = p.second, c = p.first;
    if (n == N) return true;
    for (int i = 1; i <= N; i++)
      if (Cap[n][i] && c < d[i]) {
        d[i] = c;
        From[i] = n;
        T[i] = 0;
        q.push(make_pair(c, i));
      }
    for (int v : E[n])
      if (c + 1 < d[v]) {
        d[v] = c + 1;
        From[v] = n;
        T[v] = 1;
        q.push(make_pair(c + 1, v));
      }
  }
  return false;
}
int main() {
  cin >> N >> K;
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++) {
      cin >> Cap[i][j];
      if (Cap[i][j]) E[i].push_back(j);
    }
  while (true) {
    if (!dijkstra()) break;
    int cost = 0, flow = 1000000, n = N;
    while (From[n] > 0) {
      if (T[n] == 0) flow = min(flow, Cap[From[n]][n]);
      n = From[n];
    }
    n = N;
    while (From[n] > 0) {
      if (T[n])
        cost++;
      else
        Cap[From[n]][n] -= flow, Cap[n][From[n]] += flow;
      n = From[n];
    }
    if (cost * flow <= K) {
      K -= cost * flow;
      Ans += flow;
    } else {
      Ans += K / cost;
      break;
    }
  }
  cout << Ans;
}
