#include <bits/stdc++.h>
using namespace std;
int n;
struct edge {
  int x, y, cap, flow, cost;
};
struct MinCostMaxFlow {
  int n, S, T;
  vector<vector<int> > a;
  vector<int> dist, prev, done;
  vector<edge> e;
  MinCostMaxFlow() {}
  MinCostMaxFlow(int n, int S, int T) {
    this->n = n;
    this->S = S;
    this->T = T;
    a = vector<vector<int> >(n + 1);
    dist = vector<int>(n + 1);
    prev = vector<int>(n + 1);
    done = vector<int>(n + 1);
  }
  void addEdge(int x, int y, int _cap, int _cost) {
    edge e1 = {x, y, _cap, 0, _cost};
    edge e2 = {y, x, 0, 0, -_cost};
    a[x].push_back(e.size());
    e.push_back(e1);
    a[y].push_back(e.size());
    e.push_back(e2);
  }
  pair<int, int> dijkstra() {
    int flow = 0, cost = 0;
    for (int i = 1; i <= n; i++) done[i] = 0, dist[i] = 10000007;
    priority_queue<pair<int, int> > q;
    dist[S] = 0;
    prev[S] = -1;
    q.push(make_pair(0, S));
    while (!q.empty()) {
      int x = q.top().second;
      q.pop();
      if (done[x]) continue;
      done[x] = 1;
      for (int i = 0; i < int(a[x].size()); i++) {
        int id = a[x][i], y = e[id].y;
        if (e[id].flow < e[id].cap) {
          int D = dist[x] + e[id].cost;
          if (!done[y] && D < dist[y]) {
            dist[y] = D;
            prev[y] = id;
            q.push(make_pair(-dist[y], y));
          }
        }
      }
    }
    if (done[T]) {
      flow = 10000007;
      for (int id = prev[T]; id >= 0; id = prev[e[id].x]) {
        flow = min(flow, e[id].cap - e[id].flow);
      }
      if (dist[T] > 0) {
        flow = min(flow, 1);
      }
      for (int id = prev[T]; id >= 0; id = prev[e[id].x]) {
        cost += e[id].cost * flow;
        e[id].flow += flow;
        e[id ^ 1].flow -= flow;
      }
    }
    return make_pair(flow, cost);
  }
  pair<int, int> minCostMaxFlow(int k) {
    int totalFlow = 0, totalCost = 0;
    while (1) {
      pair<int, int> u = dijkstra();
      if (!done[T]) break;
      if (totalCost + u.second > k) break;
      totalFlow += u.first;
      totalCost += u.second;
    }
    return make_pair(totalFlow, totalCost);
  }
};
int main() {
  int k;
  cin >> n >> k;
  MinCostMaxFlow maxFlow(n, 1, n);
  for (int i = 0, _i = (n); i < _i; ++i) {
    for (int j = 0, _j = (n); j < _j; ++j) {
      int temp;
      cin >> temp;
      if (temp != 0) {
        maxFlow.addEdge(i + 1, j + 1, k, 1);
        maxFlow.addEdge(i + 1, j + 1, temp, 0);
      }
    }
  }
  pair<int, int> ans = maxFlow.minCostMaxFlow(k);
  cout << ans.first << endl;
  return 0;
}
