#include<iostream>
#include<fstream>
using namespace std;
struct obiect {int g,c;};
obiect a[20];
int n,G,p[20][20],C[20][20];
fstream f("pd4.txt",ios::in);
void init()
{ int i,j;
for(i=0;i<=4;i++)
for(j=0;j<=10;j++)
{ C[i][j]=0; p[i][j]=0; }
}
void citeste()
{ int i; f>>n>>G;
for(i=1;i<=n;i++) f>>a[i].g>>a[i].c;
f.close();
cout<<n<<' '<<G<<' '<<endl;
for(i=1;i<=n;i++)
cout<<a[i].g<<' '<<a[i].c<<endl;
}
void p_dinamica()
{ int i,j;
C[1][1]=0; p[1][1]=0;
for(j=2;j<=10;j++) C[1][j]=a[1].c;
for(j=2;j<=10;j++) p[1][j]=1;
for(i=2;i<=n;i++)
{ for(j=1;j<=G;j++)
{ if((a[i].g<=j) && (a[i].c+C[i-1][j-a[i].g]>C[i-1][j]) && i>1)
{C[i][j]=a[i].c+C[i-1][j-a[i].g]; p[i][j]=i;}
else {C[i][j]=C[i-1][j]; p[i][j]=p[i-1][j];}
}
}
}
void afiseaza()
{ int i=n,j=G,k;
cout<<"profit total "<<C[n][G]<<endl;
while(p[i][j]!=0)
{ k=p[i][j];
cout<<"Obiectul "<<k<<" Cu greutatea "<<a[k].g;
cout<<" si profitul "<<a[k].c<<endl;
j-=a[p[i][j]].g;
while(p[i][j]==k) i--;
}
for(i=1;i<=4;i++)
{ for(j=1;j<=10;j++) cout<<C[i][j]<<' ';
cout<<endl;
}
}
int main()
{citeste();
p_dinamica();
afiseaza();
return 0;
}