include <bits/stdc++.h>

using namespace std;
long long f[1001][1001];
int n,M,a[1001],b[1001];
void nhap(){
cin>>n>>M;
for(int i=1;i<=n;i++)
cin>>a[i]>>b[i];
}
void qhd(){
for(int i=0;i<=n;i++)
for(int j=0;j<=M;j++)
f[i][j]=0;
for(int i=1;i<=n;i++)
for(int j=0;j<=M;j++){
f[i][j]=f[i-1][j];
if(a[i]<=j)
f[i][j]=max(f[i][j], f[i-1][j-a[i]]+b[i]);
}
}
void inbang(){
cout<<f[n][M]<<endl;
for(int i=1;i<=n;i++){
for(int j=0;j<=M;j++){
cout<<f[i][j]<<" ";
}
cout<<endl;
}
}
void truyvet(){
cout<<"Truy vet"<<endl; int i=n, j=M; while(i>0){
if(a[i]<=j && f[i][j]==f[i-1][j-a[i]]+b[i]){
cout<<1<<" <--";
j-=a[i];
}else{
cout<<0<<" <--";
}
i--;
}
cout<<endl; for(int k=n;k>=1;k--)
cout<<k<<" ";
}
int main(){
nhap();
qhd();
inbang();
truyvet();
return 0;
}