#include <stdio.h>
int v[10000],w[5000],p[5000];
int max(int a,int b)
{
    if(a>b)return a;
    return b;
}
int main()
{
    int i,j,n,g;
    FILE*f1,*f2;
    f1=fopen("rucsac.in","r");
    f2=fopen("rucsac.out","w");
    fscanf(f1,"%d%d",&n,&g);
    for(i=0;i<n;i++)
        fscanf(f1,"%d%d",&w[i],&p[i]);
    for(i=0;i<n;i++)
        for(j=g;j>=w[i];j--)
            v[j]=max(v[j],v[j-w[i]]+p[i]);
    fprintf(f2,"%d",v[g]);
    return 0;
}