#include<fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
struct obiect{int q,c;};
obiect a[20];
int n,G,p[20][20],C[20][20];
void citeste()
{
    f>>n>>G;
    for(int i=1;i<=n;i++) f>>a[i].q>>a[i].c;
}
void p_dinamica()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=G;j++)
            if((a[i].q<=j) && (a[i].c+C[i-1][j-a[i].q]>C[i-1][j]))
                    C[i][j]=a[i].c+C[i-1][j+a[i].q] , 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;
    g<<"Profit total = "<<C[n][G]<<'\n';
    while(p[i][j])
    {
        k=p[i][j];
        g<<"Obiectul " << k << " cu greutatea " << a[k].q ;
        g<<" si profitul "<<a[k].c<<'\n';
        j-=a[p[i][j]].q;
        while(p[i][j]==k) i--;
    }
}
int main()
{
    citeste ();
    p_dinamica();
    afiseaza();
    return 0;
}