#include <bits/stdc++.h>
using namespace std;
const int N = 50;
const int INF = 1 << 29;
struct edge {
  int from, to, cap, flow, cost;
  edge(int f, int t, int ca, int co) : from(f), to(t), cap(ca), cost(co) {
    flow = 0;
  }
};
vector<edge> edges;
vector<int> g[N];
void addEdge(int from, int to, int cap, int cost) {
  g[from].push_back(edges.size());
  edges.push_back(edge(from, to, cap, cost));
  g[to].push_back(edges.size());
  edges.push_back(edge(to, from, 0, -cost));
}
int n, k, s = 0, t;
int d[N], p[N];
pair<int, int> minCostFlow() {
  pair<int, int> ans = make_pair(0, 0);
  for (int flow = 0, flowCost = 0;; ++flow) {
    for (int i = 0; i < n; ++i) d[i] = INF;
    d[s] = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < edges.size(); ++j) {
        edge e = edges[j];
        if (e.cap > e.flow && d[e.from] < INF && d[e.to] > d[e.from] + e.cost) {
          d[e.to] = d[e.from] + e.cost;
          p[e.to] = j;
        }
      }
    }
    if (d[t] == INF) return make_pair(flowCost, flow);
    flowCost += d[t];
    if (flowCost > k) return ans;
    ans = make_pair(flowCost, flow);
    for (int v = t; v != s; v = edges[p[v]].from) {
      int i = p[v];
      edges[i].flow += 1;
      edges[i ^ 1].flow -= 1;
    }
  }
}
int q[N], ptr[N];
bool bfs() {
  memset(d, -1, N * sizeof(int));
  int qH = 0, qT = 0;
  q[qT++] = s;
  d[s] = 0;
  while (qH < qT) {
    int v = q[qH++];
    for (int i = 0; i < g[v].size(); ++i) {
      edge ed = edges[g[v][i]];
      if (ed.cost == 0 && d[ed.to] < 0 && ed.cap > ed.flow) {
        d[ed.to] = d[v] + 1;
        q[qT++] = ed.to;
      }
    }
  }
  return d[t] >= 0;
}
long long int dfs(int from, long long int flow) {
  if (flow == 0 || from == t) return flow;
  for (; ptr[from] < g[from].size(); ++ptr[from]) {
    int id = g[from][ptr[from]];
    if (edges[id].cost == 0 && d[from] + 1 == d[edges[id].to] &&
        edges[id].cap > edges[id].flow) {
      long long int df =
          dfs(edges[id].to, min(flow, 0ll + edges[id].cap - edges[id].flow));
      if (df) {
        edges[id].flow += df;
        edges[id ^ 1].flow -= df;
        return df;
      }
    }
  }
  return 0;
}
long long int maxFlow() {
  long long int flow = 0;
  while (bfs()) {
    memset(ptr, 0, N * sizeof(int));
    while (1) {
      long long int df = dfs(s, INF);
      if (df)
        flow += df;
      else
        break;
    }
  }
  return flow;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n >> k;
  t = n - 1;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      int temp;
      cin >> temp;
      if (temp > 0) {
        addEdge(i, j, temp, 0);
        addEdge(i, j, k * k, 1);
      }
    }
  }
  long long int ans = maxFlow();
  ans += minCostFlow().second;
  if (k > 0 && ans > 0) ++ans;
  cout << ans;
  return 0;
}
