#include <bits/stdc++.h>
using namespace std;
inline int in() {
  int32_t x;
  scanf("%d", &x);
  return x;
}
inline long long lin() {
  long long x;
  scanf("%lld", &x);
  return x;
}
const int maxn = 100 + 10;
int n, k;
int c[maxn][maxn];
bool ok[maxn][maxn];
struct flow {
  vector<int> g[maxn];
  struct edge {
    int to, cap, weight;
  } e[maxn * maxn * 5];
  int sz = 0;
  int di[maxn], used[maxn];
  inline void add(int from, int to, int cap, int weight) {
    g[from].push_back(sz);
    e[sz++] = {to, cap, weight};
  }
  inline void add_edge(int v, int u) {
    add(v, u, c[v][u], 0);
    add(u, v, c[u][v], 0);
  }
  int q[maxn * maxn], t, h;
  pair<int, int> pre[maxn];
  int mini_on_path[maxn];
  inline int max_flow(int lim) {
    int ret = 0;
    while (true) {
      for (int i = 2; i <= n; i++) used[i] = 0, di[i] = 1000000000;
      t = h = 0;
      q[t++] = 1;
      di[1] = 0;
      mini_on_path[1] = 1e9;
      while (h < t) {
        int v = q[h++];
        used[v] = false;
        for (int i = 0; i < g[v].size(); i++) {
          int nxt = e[g[v][i]].to;
          if (!((ok[v][nxt] || e[g[v][i]].cap) &&
                di[nxt] > di[v] + (e[g[v][i]].cap == 0)))
            continue;
          di[nxt] = di[v] + (e[g[v][i]].cap == 0);
          pre[nxt] = {v, g[v][i]};
          mini_on_path[nxt] = 1;
          mini_on_path[nxt] = min(mini_on_path[v], max(e[g[v][i]].cap, 1));
          if (!used[nxt]) {
            used[nxt] = true;
            q[t++] = nxt;
          }
        }
      }
      if (di[n] > lim) return ret;
      lim -= di[n];
      ret += mini_on_path[n];
      int cur = n;
      while (cur - 1) {
        int preedgeid = pre[cur].second;
        e[preedgeid].cap = max(0, e[preedgeid].cap - mini_on_path[n]);
        e[preedgeid ^ 1].cap++;
        cur = pre[cur].first;
      }
    }
  }
} mxflow;
int32_t main() {
  n = in(), k = in();
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      c[i][j] = in();
      ok[i][j] = bool(c[i][j]);
    }
  for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++) mxflow.add_edge(i, j);
  cout << mxflow.max_flow(k) << "\n";
}
