#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9+10;
const int maxn = 21;
const int maxm = (1<<20)+5;
int n, k;
int d[maxn][maxn];
void floyd_warshall(){
for(int k=0; k<n; k++){
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
}
}
}
}
int dp[maxm][maxn];
int solve(int mask, int i, int total, bool first){
if(total >= (n-k+1)) return dp[mask][i] = 0;
if(mask == (1 << n) -1) return dp[mask][i] = inf;
if(dp[mask][i] != -1) return dp[mask][i];
int ans=inf;
for(int v=0; v<n; v++){
if(mask & (1<<v) || (d[i][v]==-1 && !first)) continue;
if(first) d[i][v] = 0;
int curr = inf;
for(int u=0; u<n; u++){
if(mask & (1<<u)) continue;
curr = min(curr, (solve(mask | (1<<u), u, total+1, false)+d[i][v]));
}
ans = min(ans, curr);
}
return dp[mask][i] = ans;
}
int main() {
cin >> n >> k;
memset(dp, -1, sizeof(dp));
memset(d, -1, sizeof(d));
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cin >> d[i][j];
}
}
floyd_warshall();
int ans= solve(0, n, 0, true);
cout << ans << "\n";
}
