#include<bits/stdc++.h> using namespace std; #define int long long #define endl "\n" int mnc[1<<18][19],mnw[1<<18][19]; int w[19][19],c[19][19]; vector<int>NOW,ANS; int res=1e18; int n,m; inline void dfs(int dep,int sc,int sw,int lst,int S){ if(dep==n){ if(sc<=m&&sw<res){ res=sw; ANS=NOW; } return ; } if(lst&&sc+mnc[S][lst]>m)return; if(lst&&sw+mnw[S][lst]>res)return ; for(int i=1;i<=n;i++) if(!((S>>i-1)&1)) NOW.push_back(i), dfs(dep+1,sc+c[lst][i],sw+w[lst][i],i,S|(1<<i-1)), NOW.pop_back(); } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // freopen("genshin.in","r",stdin); // freopen("genshin.out","w",stdout); cin>>n>>m; 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(mnw,0x3f,sizeof(mnw)); memset(mnc,0x3f,sizeof(mnc)); const int N=(1<<n)-1; for(int i=1;i<=n;i++) mnw[N][i]=mnc[N][i]=0; for(int S=N;S>=0;S--) for(int i=1;i<=n;i++) if((S>>i-1)&1) for(int j=1;j<=n;j++) if(i!=j&&((S>>j-1)&1)){ mnw[S^(1<<i-1)][j]=min(mnw[S^(1<<i-1)][j],mnw[S][i]+w[j][i]); mnc[S^(1<<i-1)][j]=min(mnc[S^(1<<i-1)][j],mnc[S][i]+c[j][i]); } dfs(0,0,0,0,0); cout<<res<<endl; for(int x:ANS) cout<<x<<" "; cout<<endl; cout.flush(); return 0; }