#include <bits/stdc++.h>
using namespace std;
int n,k;
int a[23][23],visited[23],cmin=INT_MAX,ans=INT_MAX,space=0;
void backtrack(int curr,int index,int u){
    if(index==2*n){
        ans=min(ans,curr+a[u][0]);
        return;
    }
    if(curr+(2*n-index+1)*cmin>=ans){
        return;
    }
    for(int i=1;i<=2*n;i++){
        if(!visited[i]){
            if(i<=n){
                if(space<k){
                    visited[i]=1;
                    space++;
                    backtrack(curr+a[u][i],index+1,i);
                    visited[i]=0;
                    space--;
                }else{
                    continue;
                }
            }else{
                if(visited[i-n]){
                    space--;
                    visited[i]=1;
                    backtrack(curr+a[u][i],index+1,i);
                    space++;
                    visited[i]=0;
                }
            }
        }else{
            continue;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    //visited[0]=1;
    for(int i=0;i<=2*n;i++){
        for(int j=0;j<=2*n;j++){
            cin >> a[i][j];
            if(i!=j){
                cmin=min(cmin,a[i][j]);
            }
        }
    }
    backtrack(0,0,0);
    cout << ans;
}