#include<bits/stdc++.h> using namespace std; int n,m,w[20][20],c[20][20]; int W[20][300000],C[20][300000]; int ans=2e9; vector<int>an,v; void dfs(int p,int vis,int sumw,int summ){ // cout<<sumw+W[p][vis]<<" "<<summ+C[p][vis]<<endl; if(sumw+W[p][vis]>=ans)return; if(summ+C[p][vis]>m)return; // cout<<p<<" "<<vis<<endl; if(vis==(1<<n)-1){ ans=sumw; an=v; return; } for(int i=1;i<=n;i++){ if(vis>>(i-1)&1)continue; v.push_back(i); dfs(i,vis|(1<<i-1),sumw+w[p][i],summ+c[p][i]); v.pop_back(); } return; } void slv(){ cin>>n>>m; // cout<<n<<endl; 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(W,0x3f,sizeof(W)), memset(C,0x3f,sizeof(C)); for(int i=1;i<=n;i++)W[i][(1<<n)-1]=C[i][(1<<n)-1]=0; for(int i=(1<<n)-1;i>=0;i--){ for(int j=1;j<=n;j++){ if(((i>>j-1)&1)==0)continue; for(int k=1;k<=n;k++){ if(i>>(k-1)&1)continue; W[j][i]=min(W[j][i],w[j][k]+W[k][i|(1<<k-1)]); C[j][i]=min(C[j][i],c[j][k]+C[k][i|(1<<k-1)]); } // cout<<W[j][i]<<" "; } // cout<<endl; } for(int i=1;i<=n;i++){ // cout<<1<<endl; v.push_back(i); dfs(i,1<<i-1,0,0); v.pop_back(); } cout<<ans<<endl; for(int x:an)cout<<x<<" "; } int main(){ //freopen("wizard.in","r",stdin); //freopen("wizard.out","w",stdout); slv(); // cerr<<clock()*1.0/CLOCKS_PER_SEC<<endl; return 0; }