#include <bits/stdc++.h>
using namespace std;
void solve();
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}
int cost[123][123];
pair<int, int> C[123][123][5];
int bl[123];
int G[7], iG = 0, n;
int ans = (int)2e9 + 7;
inline int get_cost(int i, int j) {
  for (int t = 0; t < 5; t++)
    if (C[i][j][t].second != -1 && !bl[C[i][j][t].second])
      return C[i][j][t].first;
  return (int)2e9;
}
int cur[6][6];
int dp[6][6];
int maxlen;
void upd(int &a, int b) {
  if (a > b) a = b;
}
void gen(int pos, int k, int ind) {
  if (k == 0) {
    for (int i = 0; i < iG; i++)
      for (int j = 0; j < iG; j++) cur[i][j] = get_cost(G[i], G[j]);
    fill(dp[0], dp[0] + iG, (int)2e9);
    dp[0][0] = 0;
    for (int len = 0; len < maxlen; len++) {
      fill(dp[len + 1], dp[len + 1] + iG, (int)2e9);
      for (int i = 0; i < iG; i++)
        if (dp[len][i] != (int)2e9) {
          for (int j = 0; j < iG; j++)
            if (cur[i][j] != (int)2e9) {
              upd(dp[len + 1][j], dp[len][i] + cur[i][j]);
            }
        }
    }
    ans = min(ans, dp[maxlen][0]);
  } else {
    for (int i = pos + 1; i <= n - k; i++) {
      if (ind == 0 && i > 0) break;
      bl[i] = 1;
      G[iG++] = i;
      gen(i, k - 1, ind + 1);
      bl[i] = 0;
      iG--;
    }
  }
}
void solve() {
  cin >> n >> maxlen;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> cost[i][j];
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      vector<pair<int, int>> cur;
      for (int t = 0; t < n; t++)
        if (i != t && t != j) cur.emplace_back(cost[i][t] + cost[t][j], t);
      sort(cur.begin(), cur.end());
      for (int t = 0; t < min(5, (int)cur.size()); t++) C[i][j][t] = cur[t];
      for (int t = (int)cur.size(); t < 5; t++) C[i][j][t] = {-1, -1};
    }
  }
  maxlen /= 2;
  for (int t = 1; t <= min(n, maxlen); t++) {
    gen(-1, t, 0);
  }
  cout << ans << "\n";
}
