#include <bits/stdc++.h>
using namespace std;
auto SEED = chrono::steady_clock::now().time_since_epoch().count();
mt19937 rng(SEED);
int main() {
  int n, k;
  cin >> n >> k;
  int dist[n][n];
  for (int i = (0); i < (n); i++) {
    for (int j = (0); j < (n); j++) {
      cin >> dist[i][j];
    }
  }
  int t = 0;
  int color[n];
  long long int ans = 1ll << 60;
  while (t < 5000) {
    for (int i = (0); i < (n); i++) {
      int tt = uniform_int_distribution<int>(1, n)(rng);
      color[i] = tt & 1;
    }
    long long int dp[n][k];
    for (int j = (0); j < (k + 1); j++) {
      for (int i = (0); i < (n); i++) {
        if (j) {
          dp[i][j] = 1ll << 60;
          for (int l = (0); l < (n); l++) {
            if (color[i] + color[l] == 1) {
              dp[i][j] = min(dp[i][j], dp[l][j - 1] + dist[l][i]);
            }
          }
        } else {
          if (i)
            dp[i][j] = 1ll << 60;
          else
            dp[i][j] = 0;
        }
      }
    }
    ans = min(ans, dp[0][k]);
    t++;
  }
  cout << ans << endl;
}
