#include<bits/stdc++.h> #define ctz __builtin_ctz using namespace std; inline int lb(int x){return x&(-x);} const int N=22; int n,m; int w[N][N]; int c[N][N]; int p[N]; int ap[N]; int AW=1e9+1; inline void sub1(){ for(int i=1;i<=n;i++)p[i]=i; do{ int CC=0; int CW=0; for(int i=1;i<=n-1;i++){ CW+=w[p[i]][p[i+1]]; CC+=c[p[i]][p[i+1]]; } if(CC>m)continue; if(CW<AW){ AW=CW; for(int i=1;i<=n;i++)ap[i]=p[i]; } }while(next_permutation(p+1,p+n+1)); cout<<AW<<endl; for(int i=1;i<=n;i++)cout<<ap[i]<<" "; return; } int P[N]; bool vis[N]; int ans=1e9+1; bool flg; int q[N]; int dfn; int dfn1; inline void DFS(int S,int t,int CS,int WS){ if(WS>=ans||CS>m)return; if(dfn1>=2e5)return; if(t==n){ ++dfn1; ans=WS; for(int i=1;i<=n;i++)ap[i]=P[i]; return; } int K=S; while(K){ int nxt=ctz(K); vis[q[nxt+1]]=1;P[t+1]=q[nxt+1]; DFS(S^(1<<nxt),t+1,CS+c[P[t]][P[t+1]],WS+w[P[t]][P[t+1]]); vis[q[nxt+1]]=P[t+1]=0; K-=lb(K); } } inline void sub2(){ DFS((1<<n)-1,0,0,0); cout<<ans<<endl; for(int i=1;i<=n;i++)cout<<ap[i]<<" "; cout<<endl; } signed main(){ #ifndef ONLINE_JUDGE freopen("wizard.in","r",stdin); freopen("wizard.out","w",stdout); #endif cin>>n>>m; for(int i=1;i<=n;i++)q[i]=i; random_shuffle(q+1,q+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]; if(n<=10){sub1();return 0;} sub2(); return 0; }