#include<cstdio>
using namespace std;
int n,G,p[10001][10001],c[10001][10001];
struct obiect
{
    int gr,cost;
};
obiect v[100];
void citire()
{
    freopen("rucsac.in","rt",stdin);
    scanf("%d%d",&n,&G);
    for(int i=1;i<=n;++i)
    scanf("%d%d",&v[i].gr,&v[i].cost);
}
void pd()
{
    for(int i=1;i<=n;++i)
    for(int j=1;j<=G;++j)
    if(v[i].gr<=j&&v[i].cost+c[i-1][j-v[i].gr]>c[i-1][j])
    {c[i][j]=v[i].cost+c[i-1][j-v[i].gr];
    p[i][j]=i;
    }
    else{
    c[i][j]=c[i-1][j];
    p[i][j]=p[i-1][j];
    }
}
void afis()
{
    int i=n,j=G,k;
    freopen("rucsac.out","wt",stdout);
    printf("profit=%d\n",c[n][G]);
    while(p[i][j]!=0)
{
    k=p[i][j];
    printf("ob%d gr%d  cost%d \n",k,v[k].gr,v[k].cost);
    j-=v[p[i][j]].gr;
    while(p[i][j]==k)
    --i;
}
}
int main()
{
    citire();
    pd();
    afis();
    return 0;
}