#include<bits/stdc++.h> using namespace std; #define int long long int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=20,inf=1000000000; string ejz(int x){ string s=""; for(int i=3;~i;i--)s+=x&(1<<i)?"1":"0"; return s; } int n,m,ans,c[MAXN][MAXN],w[MAXN][MAXN],p[MAXN],a[MAXN],as[MAXN],id[MAXN][MAXN],f[1<<MAXN][MAXN]; void dfs(int now,int x,int sum,int num,int S){ // cout<<ejz(S)<<" "<<now<<" "<<x<<" "<<sum<<" "<<num<<endl; if(num+f[S][x]>m)return; if(sum>=ans)return; if(now==n+1){ ans=sum; for(int i=1;i<=n;i++){ as[i]=a[i]; } return; } for(int i=1;i<=n;i++)if(!p[i]){ p[i]=1; a[now]=i; dfs(now+1,i,sum+c[x][i],num+w[x][i],S|(1<<i-1)); p[i]=0; } } int tot; bool cmp(int x,int y){return c[tot][x]+w[tot][x]<c[tot][y]+w[tot][y];} void slv(){ n=read(),m=read();ans=inf; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)c[i][j]=read(); for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)w[i][j]=read(); memset(f,0x3f,sizeof(f)); for(int i=1;i<=n;i++)f[(1<<n)-1][i]=0; f[0][0]=0; for(int i=(1<<n)-1;~i;i--){ for(int j=1;j<=n;j++)if((1<<j-1)&i){ for(int o=1;o<=n;o++)if(((1<<o-1)&i)&&(o!=j)){ f[i^(1<<j-1)][o]=min(f[i][j]+w[o][j],f[i^(1<<j-1)][o]); } } } // for(int i=(1<<n)-1;i;i--){ // for(int j=1;j<=n;j++)if((1<<j-1)&i){ // cout<<ejz(i)<<" "<<j<<" "<<f[i][j]<<endl; // } // } dfs(1,0,0,0,0); if(ans==inf){ printf("-1"); return; } printf("%lld\n",ans); for(int i=1;i<=n;i++)printf("%lld ",as[i]); } signed main(){ slv(); return 0; }