#include<bits/stdc++.h>
using namespace std;
#define MAX 100
#define ifi 1000*10000+4
int n,k;
int c[MAX][MAX];//ma tran goc
int x[MAX];//bang thu
int f,bestf=ifi;//best path
int cmin=ifi;
int Free[MAX];//ma tran kiem tra da di qua hay chua
set<int> s;
void input(){
	int i,j;
	cin>>n>>k;
	for(i=0;i<=2*n;i++){
		for(j=0;j<=2*n;j++)
		{	cin>>c[i][j];
			if(i!=j) cmin=min(cmin,c[i][j]);
		}
	}
	for(i=1;i<=2*n;i++){
		Free[i]=1;	
	}
	Free[0]=0;
	x[0]=0;
	f=0;
}//bai toan tro thanh bai tsp vs 2n diem va kthuc kkhi ko con khach
void solve(int i){
	for(int j=1;j<=2*n;j++){
		if(Free[j]){
			x[i]=j;
			Free[j]=0;
			if(j>=1 && j<=n && s.size()<k && s.find(j)==s.end() ) s.insert(j);// neu xe con cho thi don khach len
			if(j>n){ // gap dung cho thi tra khach
				auto tmp = s.find(j-n);
				if(tmp!=s.end()) s.erase(tmp);
			}
			f+=c[x[i-1]][x[i]];//tu vi tri trc do den vi tri j
			if(i==2*n && s.size()==0) {
				if(f + c[x[2*n]][0] < bestf) bestf = f + c[x[2*n]][0];
			}
			else{
				if(f + (2*n-i+1)*cmin < bestf ) solve(i+1); //khi den vi tri i thi con 2n-i+1 lan di chuyen nua
			}
			f-=c[x[i-1]][x[i]];//tro lai ban dau
			if(j>=1 && j<=n && s.find(j)!=s.end()) s.erase(s.find(j)); //neu da dua len thi tra lai 
			if(j>n && s.find(j-n)==s.end() && s.size()<k ) s.insert(j-n);//neu da tra thi dua len
			Free[j]=1;
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	input();
	solve(1);
	cout<<bestf;
}