#include<cstdio>
using namespace std;

int n ,G,p[10001][10001],c[10001][10001];

struct{ int gr, cost;}v[10001];

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 afisare(){

int i=n,j=G,k;

freopen("rucsac.out","wt",stdout);
printf("%d\n",c[n][G]);

while(p[i][j]){

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();

afisare();

return 0;

}