#include<bits/stdc++.h> using namespace std; const int N=22,S=3e5+10,INF=1e9+10; int vis[N];int ans=INF; int A[N];int n,m; int sel[N]; int w[N][N],c[N][N]; int f[N][S];int g[N][S]; bool cmp(){ for(int i=1;i<=n;i++){ if(sel[i]<A[i]) return 1; if(sel[i]>A[i]) return 0; }return 0; }int ALL=0; void dfs(int x,int la,int stt,int now,int cst){ if(now+g[la][ALL^stt]>ans) return ; //cout<<stt<<' '<<la<<endl; if(cst+f[la][ALL^stt]>m) return ; //if(x>9) return ; if(x>n){ if(now<ans){ ans=now; for(int i=1;i<=n;i++) A[i]=sel[i]; }else if(now==ans){ if(cmp()){ for(int i=1;i<=n;i++) A[i]=sel[i]; } }return ; } if(la!=0) stt|=1<<(la-1); for(int i=1;i<=n;i++){ if(vis[i]) continue; vis[i]=1;sel[n+1-x]=i; dfs(x+1,i,stt,now+w[sel[n+1-x]][sel[n+2-x]],cst+c[sel[n+1-x]][sel[n+2-x]]); vis[i]=0; } } int main(){ //double C=clock(); cin>>n>>m;A[1]=n+1;ALL=(1<<n)-1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>w[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>c[i][j]; memset(f,0x3f,sizeof(f));f[0][ALL]=0; for(int i=1;i<=n;i++) f[i][1<<(i-1)]=0; for(int i=1;i<(1<<n);i++){ for(int j=1;j<=n;j++){ //cout<<i<<' '<<j<<' '<<f[j][i]<<endl; if((i>>(j-1))&1){ //cout<<j<<' '<<i<<endl; for(int k=1;k<=n;k++){ if((i>>(k-1))&1) continue; //cout<<(i|(1<<(k-1)))<<' '<<k<<' '<<endl; f[k][i|(1<<(k-1))]=min(f[k][i|(1<<(k-1))],f[j][i]+c[j][k]); //cout<<f[k][i|(1<<(k-1))]<<endl; } } } }memset(g,0x3f,sizeof(g));g[0][ALL]=0; for(int i=1;i<=n;i++) g[i][1<<(i-1)]=0; for(int i=1;i<(1<<n);i++){ for(int j=1;j<=n;j++){ //cout<<i<<' '<<j<<' '<<f[j][i]<<endl; if((i>>(j-1))&1){ //cout<<j<<' '<<i<<endl; for(int k=1;k<=n;k++){ if((i>>(k-1))&1) continue; //cout<<(i|(1<<(k-1)))<<' '<<k<<' '<<endl; g[k][i|(1<<(k-1))]=min(g[k][i|(1<<(k-1))],g[j][i]+w[j][k]); //cout<<f[k][i|(1<<(k-1))]<<endl; } } } }//cerr<<(clock()-C)/CLOCKS_PER_SEC; dfs(1,0,0,0,0); if(ans>=INF){ cout<<-1; }else{ cout<<ans<<endl; for(int i=1;i<=n;i++) cout<<A[i]<<' '; } //cerr<<(clock()-C)/CLOCKS_PER_SEC; return 0; }