#include <stdio.h>

using namespace std;

int pmax[10001],s[10001];

struct obiecte{
    int g,p;
}v[5001];

int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    int n,gmax,i,j,m,aux;
    scanf("%d%d",&n,&gmax);
    for(i=1;i<=n;i++)
        scanf("%d%d",&(v[i].g),&(v[i].p));

    m=0;
    s[0]=-1;
    pmax[0]=0;
    for(i=1;i<=n;i++)
    {
        for(j=m;j>=0;j--)
        {
            if(s[j]!=0&&j+v[i].g<=gmax&&pmax[j]+v[i].p>pmax[j+v[i].g])
            {
                aux=j+v[i].g;
                s[aux]=i;
                pmax[aux]=pmax[j]+v[i].p;
                if(aux>m) m=aux;
            }
        }
    }
    aux=0;
    for(i=0;i<=m;i++)
        if(pmax[i]>aux) aux=pmax[i];

    printf("%d",aux);

    return 0;
}