#include <bits/stdc++.h>
using namespace std;
template <typename flow_t, typename cost_t>
struct PrimalDual {
  struct Edge {
    int to;
    flow_t cap;
    cost_t cost;
    int rev;
    bool isrev;
    Edge(int to, flow_t cap, cost_t cost, int rev, bool isrev)
        : to(to), cap(cap), cost(cost), rev(rev), isrev(isrev) {}
  };
  const cost_t C_INF = numeric_limits<cost_t>::max();
  int n;
  vector<vector<Edge>> g;
  vector<cost_t> min_cost;
  vector<int> prevv, preve;
  cost_t ub;
  PrimalDual(int n, cost_t ub) : n(n), g(n), ub(ub) {}
  void add_edge(int from, int to, flow_t cap, cost_t cost) {
    g[from].emplace_back(Edge(to, cap, cost, g[to].size(), false));
    g[to].emplace_back(Edge(from, 0, -cost, g[from].size() - 1, true));
  }
  void add_edge(int from, int to, cost_t cost) {
    if (cost > 0) add_edge(from, to, cost, 0), add_edge(from, to, ub, 1);
  }
  cost_t dijkstra(int s, int t) {
    using Pi = pair<cost_t, int>;
    priority_queue<Pi, vector<Pi>, greater<Pi>> pq;
    min_cost.assign(n, C_INF), min_cost[s] = 0;
    pq.emplace(0, s);
    while (!pq.empty()) {
      Pi p = pq.top();
      pq.pop();
      if (min_cost[p.second] < p.first) continue;
      for (int i = 0; i < (int)g[p.second].size(); i++) {
        Edge &e = g[p.second][i];
        if (min_cost[e.to] > min_cost[p.second] + e.cost && e.cap > 0) {
          min_cost[e.to] = min_cost[p.second] + e.cost;
          prevv[e.to] = p.second, preve[e.to] = i;
          pq.emplace(min_cost[e.to], e.to);
        }
      }
    }
    return min_cost[t];
  }
  pair<flow_t, cost_t> max_flow(int s, int t) {
    flow_t flow = 0;
    cost_t cost = 0;
    preve.assign(n, -1), prevv.assign(n, -1);
    while (true) {
      if (dijkstra(s, t) == C_INF) return {flow, cost};
      flow_t addflow = numeric_limits<flow_t>::max();
      cost_t cst = 0;
      for (int v = t; v != s; v = prevv[v]) {
        addflow = min(addflow, g[prevv[v]][preve[v]].cap);
        cst += g[prevv[v]][preve[v]].cost;
      }
      if (cst > ub) return {flow, cost};
      if (cst) addflow = min(addflow, ub / cst);
      ub -= addflow * cst, cost += addflow * cst, flow += addflow;
      for (int v = t; v != s; v = prevv[v]) {
        Edge &e = g[prevv[v]][preve[v]];
        g[v][e.rev].cap += addflow, e.cap -= addflow;
      }
    }
  }
  friend ostream &operator<<(ostream &os, PrimalDual &mcf) {
    for (int i = 0; i < (int)mcf.g.size(); i++) {
      for (auto &e : mcf.g[i])
        if (!e.isrev) {
          auto &rev_e = mcf.g[e.to][e.rev];
          os << i << " -> " << e.to << " (flow: " << rev_e.cap << " / ";
          os << e.cap + rev_e.cap << ", cost: " << e.cost << ")" << endl;
        }
    }
    return os;
  }
};
int main() {
  int n, k;
  cin >> n >> k;
  PrimalDual<int, int> mcf(n, k);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      int c;
      cin >> c;
      mcf.add_edge(i, j, c);
    }
  cout << mcf.max_flow(0, n - 1).first << endl;
  return 0;
}
