#include <bits/stdc++.h>
using namespace std;
const long long maxn = 90;
vector<long long> col[2];
long long savecol[maxn];
long long dis[maxn][12];
long long g[88][88];
void solve() {
  long long n, k;
  scanf("%lld %lld", &n, &k);
  for (long long i = 1; i <= n; i++)
    for (long long j = 1; j <= n; j++) scanf("%lld", &g[i][j]);
  long long t = 2000;
  long long ans = LLONG_MAX;
  while ((double)clock() / 1000 < 0.8) {
    col[0].clear();
    col[1].clear();
    for (long long i = 1; i <= n; i++) {
      savecol[i] = rand() % 2;
      col[savecol[i]].push_back(i);
    }
    memset(dis, 0x3f, sizeof(dis));
    dis[1][0] = 0;
    for (long long nowk = 1; nowk <= k; nowk++) {
      for (long long s = 1; s <= n; s++) {
        for (long long d : col[savecol[s] ^ 1]) {
          dis[d][nowk] = min(dis[d][nowk], dis[s][nowk - 1] + g[s][d]);
        }
      }
    }
    ans = min(ans, dis[1][k]);
  }
  cout << ans << endl;
}
signed main() {
  srand(time(NULL));
  solve();
}
