#include <bits/stdc++.h>
using namespace std;
const int oo = 0x3f3f3f3f;
const double eps = 1e-9;
int M, K;
struct Edge {
  int to;
  long long residual, cost;
  bool orig;
  list<Edge>::iterator rev;
  long long len;
};
const long long INF = LLONG_MAX / 2;
const int maxN = 108;
int N, SRC, DST;
long long dist[maxN], pot[maxN];
list<Edge>::iterator pred[maxN];
list<Edge> out[maxN];
void reset(int n, int s, int t) {
  N = n;
  SRC = s;
  DST = t;
  for (int i = (0); i < (N); i++) out[i].clear();
}
void add_edge(int a, int b, long long cap, long long cost) {
  Edge ab = {b, cap, cost, true, out[b].end(), 0},
       ba = {a, 0, -cost, false, out[a].end(), 0};
  out[a].push_front(ab);
  out[b].push_front(ba);
  auto e = out[a].begin();
  e->rev = out[b].begin();
  e->rev->rev = e;
}
void init_pots() {
  for (int i = (0); i < (N); i++) pot[i] = 0;
  for (int i = (0); i < (N); i++)
    for (int j = (0); j < (N); j++)
      for (const Edge &e : out[j])
        if (e.orig) {
          pot[e.to] = min(pot[e.to], pot[j] + e.cost);
        }
}
void dijkstra(int start) {
  for (int i = (0); i < (N); i++) dist[i] = INF;
  dist[start] = 0;
  set<pair<int, int>> pq;
  pq.insert(make_pair(0, start));
  while (!pq.empty()) {
    int cur = pq.begin()->second;
    pq.erase(pq.begin());
    for (const auto &e : out[cur]) {
      if (e.residual == 0) continue;
      if (cur != start && pred[cur]->to == e.to) continue;
      long long ndist = dist[cur] + e.len;
      if (ndist >= dist[e.to]) continue;
      if (dist[e.to] < INF) pq.erase(make_pair(dist[e.to], e.to));
      dist[e.to] = ndist;
      pred[e.to] = e.rev;
      pq.insert(make_pair(ndist, e.to));
    }
  }
}
long long augment(int n, long long cap, long long &cost_one) {
  if (n == SRC) return cap;
  cap = augment(pred[n]->to, min(cap, pred[n]->rev->residual), cost_one);
  pred[n]->rev->residual -= cap;
  pred[n]->residual += cap;
  cost_one += pred[n]->rev->cost;
  return cap;
}
pair<long long, long long> mcmf(long long max_cost = INF) {
  init_pots();
  long long flow = 0, cost = 0;
  while (true) {
    for (int i = (0); i < (N); i++)
      for (auto &e : out[i]) {
        e.len = e.cost + pot[i] - pot[e.to];
      }
    dijkstra(SRC);
    if (dist[DST] == INF) break;
    long long cost_one = 0;
    long long cap = augment(DST, INF, cost_one);
    cost += cost_one * cap;
    flow += cap;
    if (cost > max_cost) {
      int undo = (cost - max_cost + cost_one - 1) / cost_one;
      cost -= cost_one * undo;
      flow -= undo;
      break;
    }
    for (int i = (0); i < (N); i++) pot[i] += dist[i];
  }
  return make_pair(cost, flow);
};
int main() {
  cin >> M >> K;
  vector<tuple<int, int, int>> edge;
  for (int i = (1); i < (M + 1); i++)
    for (int j = (1); j < (M + 1); j++) {
      int tmp;
      cin >> tmp;
      if (tmp == 0) continue;
      edge.push_back(make_tuple(i, j, tmp));
    }
  reset(M + 1, 1, M);
  for (const auto &e : edge) {
    int a, b, cap;
    tie(a, b, cap) = e;
    add_edge(a, b, cap, 0);
    add_edge(a, b, 1000, 1);
  }
  auto tmp = mcmf(K);
  cout << tmp.second << endl;
}
