#include <bits/stdc++.h>
using namespace std;
bool SR(int &x) { return scanf("%d", &x) == 1; }
bool SR(long long &x) { return scanf("%lld", &x) == 1; }
bool SR(double &x) { return scanf("%lf", &x) == 1; }
bool SR(char *s) { return scanf("%s", s) == 1; }
bool RI() { return true; }
template <typename I, typename... T>
bool RI(I &x, T &...tail) {
  return SR(x) && RI(tail...);
}
void SP(const int x) { printf("%d", x); }
void SP(const long long x) { printf("%lld", x); }
void SP(const double x) { printf("%.16lf", x); }
void SP(const char *s) { printf("%s", s); }
void PL() { puts(""); }
template <typename I, typename... T>
void PL(const I x, const T... tail) {
  SP(x);
  if (sizeof...(tail)) putchar(' ');
  PL(tail...);
}
const int maxn = 52;
struct Flow {
  struct Edge {
    int v, c, f;
    Edge(int _v, int _c, int _f) : v(_v), c(_c), f(_f) {}
  };
  int n;
  vector<Edge> edge;
  vector<int> id[maxn];
  vector<int>::iterator arc[maxn];
  void init(int _n) { n = _n; }
  void add(int u, int v, int c, int f1, int f2) {
    id[u].push_back(((int)(edge).size()));
    edge.push_back(Edge(v, c, f1));
    id[v].push_back(((int)(edge).size()));
    edge.push_back(Edge(u, -c, f2));
  }
  int dep[maxn];
  bool bfs() {
    memset(dep, 0, sizeof(int) * n);
    queue<int> q;
    dep[0] = 1;
    q.push(0);
    while (((int)(q).size())) {
      int u = q.front();
      q.pop();
      for (auto i : id[u])
        if (edge[i].f > 0 && !dep[edge[i].v]) {
          dep[edge[i].v] = dep[u] + 1;
          q.push(edge[i].v);
        }
    }
    return dep[n - 1];
  }
  int dfs(int u, int w) {
    if (u == n - 1) return w;
    int ans = 0;
    for (auto &it = arc[u]; it != id[u].end(); it++)
      if (edge[*it].f > 0 && dep[edge[*it].v] == dep[u] + 1) {
        int i = *it;
        int sub = dfs(edge[i].v, min(w - ans, edge[i].f));
        ans += sub;
        edge[i].f -= sub;
        edge[i ^ 1].f += sub;
        if (ans == w) break;
      }
    return ans;
  }
  int calc() {
    int ans = 0;
    while (bfs()) {
      for (int i = 0; i < int(n); i++) arc[i] = id[i].begin();
      ans += dfs(0, 1e9);
    }
    return ans;
  }
  int pe[maxn], dis[maxn];
  int spfa() {
    memset(pe, -1, sizeof(int) * n);
    for (int i = 0; i < int(n); i++) dis[i] = 1e9;
    bitset<maxn> inq;
    queue<int> q;
    q.push(0);
    dis[0] = 0;
    inq[0] = 1;
    while (((int)(q).size())) {
      int u = q.front();
      q.pop();
      inq[u] = 0;
      for (auto i : id[u])
        if (edge[i].f > 0 && dis[edge[i].v] > dis[u] + edge[i].c) {
          dis[edge[i].v] = dis[u] + edge[i].c;
          pe[edge[i].v] = i;
          if (!inq[edge[i].v]) {
            q.push(edge[i].v);
            inq[edge[i].v] = 1;
          }
        }
    }
    for (int u = n - 1; ~pe[u]; u = edge[pe[u] ^ 1].v) {
      edge[pe[u]].f--;
      edge[pe[u] ^ 1].f++;
    }
    return dis[n - 1];
  }
  int sol(int k) {
    int ans = 0;
    while (1) {
      k -= spfa();
      if (k < 0) return ans;
      ans++;
    }
    return ans;
  }
} flow;
int n, k;
int g[maxn][maxn];
void read() {
  RI(n, k);
  flow.init(n);
  for (int i = 0; i < int(n); i++)
    for (int j = 0; j < int(n); j++) {
      RI(g[i][j]);
      if (g[i][j]) flow.add(i, j, 0, g[i][j], 0);
    }
}
void build() {}
void sol() {
  int ans = flow.calc();
  for (int i = 0; i < int(n); i++)
    for (int j = 0; j < int(n); j++)
      if (g[i][j]) {
        flow.add(i, j, 1, k, 0);
      }
  ans += flow.sol(k);
  PL(ans);
}
int main() {
  read();
  build();
  sol();
  return 0;
}
