1. #include<bits/stdc++.h>
2. using namespace std;
3. #define MAX 100
4. #define ifi 1000*10000+4
5. int n,k;
6. int c[MAX][MAX];//ma tran goc
7. int x[MAX];//bang thu
8. int f,bestf=ifi;//best path
9. int cmin=ifi;
10. int Free[MAX];//ma tran kiem tra da di qua hay chua
11. set<int> s;
12. void input(){
13.         int i,j;
14.         cin>>n>>k;
15.         for(i=0;i<=2*n;i++){
16.                 for(j=0;j<=2*n;j++)
17.                 {       cin>>c[i][j];
18.                         if(i!=j) cmin=min(cmin,c[i][j]);
19.                 }
20.         }
21.         for(i=1;i<=2*n;i++){
22.                 Free[i]=1;     
23.         }
24.         Free[0]=0;
25.         x[0]=0;
26.         f=0;
27. }//bai toan tro thanh bai tsp vs 2n diem va kthuc kkhi ko con khach
28. void solve(int i){
29.         for(int j=1;j<=2*n;j++){
30.                 if(Free[j]){
31.                         x[i]=j;
32.                         Free[j]=0;
33.                         if(j>=1 && j<=n && s.size()<k && s.find(j)==s.end() ) s.insert(j);// neu xe con cho thi don khach len
34.                         if(j>n){ // gap dung cho thi tra khach
35.                                 auto tmp = s.find(j-n);
36.                                 if(tmp!=s.end()) s.erase(tmp);
37.                         }
38.                         f+=c[x[i-1]][x[i]];//tu vi tri trc do den vi tri j
39.                         if(i==2*n && s.size()==0) {
40.                                 if(f + c[x[2*n]][0] < bestf) bestf = f + c[x[2*n]][0];
41.                         }
42.                         else{
43.                                 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
44.                         }
45.                         f-=c[x[i-1]][x[i]];//tro lai ban dau
46.                         if(j>=1 && j<=n && s.find(j)!=s.end()) s.erase(s.find(j)); //neu da dua len thi tra lai
47.                         if(j>n && s.find(j-n)==s.end() && s.size()<k ) s.insert(j-n);//neu da tra thi dua len
48.                         Free[j]=1;
49.                 }
50.         }
51. }
52. int main(){
53.         ios::sync_with_stdio(0);
54.         cin.tie(0);
55.         input();
56.         solve(1);
57.         cout<<bestf;
58. }