#include <bits/stdc++.h>
using namespace std;
struct rib {
  int from, to, cost, cap, rev;
};
bool operator<(const rib x, const rib y) { return x.cost > y.cost; }
void addEdge(vector<vector<rib> > &adj, int from, int to, int cap, int cost) {
  {
    rib r = {from, to, cost, cap, ((int)(adj[to]).size())};
    adj[from].push_back(r);
  }
  {
    rib r = {to, from, -cost, 0, ((int)(adj[from]).size()) - 1};
    adj[to].push_back(r);
  }
}
int mincostFlow(vector<vector<rib> > &adj, int s, int t, int n, int k) {
  int flow = 0;
  int cost = 0;
  while (true) {
    priority_queue<rib> q;
    vector<int> prev(n, -1);
    vector<int> prev_num(n, -1);
    rib start = {-1, s, 0, 0, 0};
    q.push(start);
    vector<int> d(n, INT_MAX);
    prev[s] = s;
    while (!q.empty()) {
      rib r = q.top();
      q.pop();
      for (int i = 0; i < ((int)(adj[r.to]).size()); i++) {
        if (d[adj[r.to][i].to] > adj[r.to][i].cost + r.cost &&
            adj[r.to][i].cap > 0) {
          prev[adj[r.to][i].to] = r.to;
          prev_num[adj[r.to][i].to] = i;
          d[adj[r.to][i].to] = adj[r.to][i].cost + r.cost;
          rib RIB = {r.to, adj[r.to][i].to, d[adj[r.to][i].to], 0, 0};
          q.push(RIB);
        }
      }
    }
    if (prev[t] == -1) return flow;
    int addFlow = INT_MAX;
    int best = 0;
    for (int v = t; v != s; v = prev[v]) {
      addFlow = min(addFlow, adj[prev[v]][prev_num[v]].cap);
      best += adj[prev[v]][prev_num[v]].cost;
    }
    if (best > k) return flow;
    if (best) addFlow = min(addFlow, k / best);
    cost += best * addFlow;
    k -= best * addFlow;
    for (int v = t; v != s; v = prev[v]) {
      adj[prev[v]][prev_num[v]].cap -= addFlow;
      adj[adj[prev[v]][prev_num[v]].to][adj[prev[v]][prev_num[v]].rev].cap +=
          addFlow;
    }
    flow += addFlow;
  }
}
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  vector<vector<rib> > adj(n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      int c;
      scanf("%d", &c);
      if (c) {
        addEdge(adj, i, j, c, 0);
        addEdge(adj, i, j, k, 1);
      }
    }
  }
  printf("%d\n", mincostFlow(adj, 0, n - 1, n, k));
  return 0;
}
