#include <bits/stdc++.h>
const int N = 60;
const int INF = (int)1e9 + 228;
using namespace std;
int n, k;
int c[N][N], f[N][N], ptr[N], pr[N];
bool used[N];
queue<int> q;
set<pair<int, int> > st;
int dp[N];
bool bfs() {
  for (int i = 1; i <= n; i++) dp[i] = -1;
  dp[1] = 0;
  q.push(1);
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int i = 1; i <= n; i++) {
      int to = i;
      if (c[v][to] > f[v][to] && dp[to] == -1) {
        dp[to] = dp[v] + 1;
        q.push(to);
      }
    }
  }
  return dp[n] != -1;
}
int dfs(int v, int flow) {
  if (flow == 0) return 0;
  if (v == n) return flow;
  for (int &i = ptr[v]; i <= n; i++) {
    int to = i;
    if (dp[to] != dp[v] + 1) continue;
    int pushed = dfs(to, min(flow, c[v][to] - f[v][to]));
    if (pushed) {
      f[v][to] += pushed;
      f[to][v] -= pushed;
      return pushed;
    }
  }
  return 0;
}
int dijkstra() {
  for (int i = 1; i <= n; i++) {
    used[i] = false;
    dp[i] = INF;
  }
  dp[1] = 0;
  int mn, id;
  for (int i = 1; i <= n; i++) {
    mn = INF;
    for (int j = 1; j <= n; j++) {
      if (dp[j] < mn && !used[j]) {
        mn = dp[j];
        id = j;
      }
    }
    if (mn == INF) break;
    used[id] = true;
    for (int j = 1; j <= n; j++) {
      if (c[id][j] && c[id][j] > f[id][j] && dp[j] > dp[id]) {
        dp[j] = dp[id];
        pr[j] = id;
      }
      if (c[id][j] && c[id][j] == f[id][j] && dp[j] > dp[id] + 1) {
        dp[j] = dp[id] + 1;
        pr[j] = id;
      }
    }
  }
  if (k < dp[n]) {
    k = 0;
    return 0;
  } else {
    k -= dp[n];
    int v = n;
    while (v != 1) {
      if (c[pr[v]][v] == f[pr[v]][v]) c[pr[v]][v]++;
      f[pr[v]][v]++;
      v = pr[v];
    }
    return 1;
  }
}
int max_flow() {
  int flow = 0;
  while (bfs()) {
    for (int i = 1; i <= n; i++) ptr[i] = 1;
    while (int pushed = dfs(1, INF)) flow += pushed;
  }
  while (k) {
    flow += dijkstra();
  }
  return flow;
}
int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) cin >> c[i][j];
  cout << max_flow();
  return 0;
}
