#include <fstream>

using namespace std;
int a[5001],p[10001],n,g,i,j,max1;
char fr[10001];
ofstream gg("rucsac.out");
int main()
{
    freopen("rucsac.in","r",stdin);
    scanf("%d%d",&n,&g);
    for(i=1;i<=n;i++){
        int pp;
        scanf("%d%d",&a[i],&pp);
        p[a[i]]=pp;
    }
    int max1=0;
    fr[0]=1;
    for(i=1;i<=n;i++)
    for(j=max1;j>=0;j--){
        if(fr[j]==1&&j+a[i]<=g)
            {fr[j+a[i]]=1;
            p[j+a[i]]=p[j]+p[a[i]];}
        max1=max1+a[i];
    }
    max1=0;
    for(i=1;i<=g;i++)
        if(p[i]>max1)
        max1=p[i];
    gg<<max1;
    return 0;
}