#include <fstream>
using namespace std;
struct obiect (int g,c;);
obiect a[20];
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,G,p[20][20],C[20][20];
void cit()
{f>>n>>G;
 for(int i=1;i<=n;i++) f>>a[i].g>>a[i].c;
 f.close();
}
void p_d()
{for(int i=1;i<=n;i++)
    for(int j=1;j<=G;j++)
        if(a[i].g<j && a[i].c+C[i-1][j-a[i].g]>C[i-1][j])
            {C[i][j]=a[i].c+C[i-1][j-a[i].g];
             p[i][j];
            }
            else {C[i][j]=C[i-1][j];
                  p[i][j]=p[i-1][j];
                 }
}
void afis()
{int i=n,j=G,k;
 g<<"Profit total= "<<C[n][G]<<'\n';
 while(p[i][j]!=0)
    {k=p[i][j];
     g<<"Obiectul"<<k<<" cu greutatea "<<a[k].g;
     g<<" si profitul "<<a[k].c<<'\n';
     j-=a[p[i][j]].g;
     while(p[i][j]==k)
        i--;
    }
}
int main()
{cit();
 p_d();
 afis();
 return 0;
}