//100pts #include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back #define ppc __builtin_popcount using namespace std; typedef long long ll; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m,w[20][20],c[20][20]; pi dp1[1<<18][18],dp2[1<<18][18],g[1<<18],gg[1<<18]; pi A; pi operator+(pi a,pi b){return m_p(a.p1+b.p1,a.p2+b.p2);} int P[20],ANS[20],used[20],val=2e9; void dfs(int x,int c1,int c2,int S){ if(c1+g[((1<<n)-1)^S].p1>m||c2+gg[((1<<n)-1)^S].p1>min(val,A.p2))return; if(x>n){ if(c2<val)val=c2,memcpy(ANS,P,sizeof(P)); else if(c2==val){ up(i,1,n)if(P[i]^ANS[i]){ if(P[i]<ANS[i])memcpy(ANS,P,sizeof(P)); break; } }return; } up(i,1,n)if(!used[i]){ used[i]=1; P[x]=i; dfs(x+1,c1+c[P[x-1]][i],c2+w[P[x-1]][i],S^(1<<(i-1))); used[i]=0; } } void slv(){ n=read(),m=read(); up(i,1,n)up(j,1,n)w[i][j]=read(); up(i,1,n)up(j,1,n)c[i][j]=read(); up(i,0,n-1)dp1[1<<i][i]=dp2[1<<i][i]=m_p(0,0); up(i,1,(1<<n)-1){ vector<int>A; down(j,n-1,0)if((i>>j)&1)A.p_b(j); if(ppc(i)==1)continue; g[i]=gg[i]=m_p(1e9,1e9); for(int x:A){ int S=i^(1<<x); dp1[i][x]=dp2[i][x]=m_p(int(1e9),int(1e9)); for(int y:A)if(x^y){ dp1[i][x]=min(dp1[i][x],dp1[S][y]+m_p(c[y+1][x+1],w[y+1][x+1])); dp2[i][x]=min(dp2[i][x],dp2[S][y]+m_p(w[y+1][x+1],c[y+1][x+1])); }g[i]=min(g[i],dp1[i][x]); gg[i]=min(gg[i],dp2[i][x]); } }A=m_p(int(1e9),int(1e9));up(i,0,n-1)A=min(A,dp1[(1<<n)-1][i]); dfs(1,0,0,0); if(val==int(2e9))cout<<"-1"; else { printf("%d\n",val); up(i,1,n)printf("%d ",ANS[i]); } } int main(){ //freopen("wizard.in","r",stdin); //freopen("wizard.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }