#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const long long N = 1e3 + 10;
const long long inf = (long long)1e18 + 10ll;
const long long mod = 1e9 + 7;
const long long eps = 1e-9;
const char spc = 29;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
using namespace std;
long long n, k;
long long a[N][N];
char c[N];
long long dp[N];
long long buf[N];
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  for (long long i = 0; i < n; ++i)
    for (long long j = 0; j < n; ++j) cin >> a[i][j];
  long long ans = inf;
  for (long long i = 0; i < (long long)1e4; ++i) {
    for (long long i = 0; i < n; ++i) c[i] = rnd() % 2;
    for (long long i = 0; i < n; ++i)
      if (c[i] == c[0])
        dp[i] = inf;
      else
        dp[i] = a[0][i];
    for (long long z = 1; z < k; ++z) {
      fill(buf, buf + n, inf);
      for (long long i = 0; i < n; ++i) {
        for (long long j = 0; j < n; ++j)
          if (c[i] != c[j]) buf[i] = min(buf[i], dp[j] + a[j][i]);
      }
      copy(buf, buf + n, dp);
    }
    ans = min(ans, dp[0]);
  }
  cout << ans << "\n";
}
