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