#include <cstdio>
#define N 5001

int n,g,sol;
int w[N],p[N],optim[10001];

int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);

    scanf("%d %d",&n, &g);
    for(int i=0; i<n; i++)
        scanf("%d %d",&w[i], &p[i]);

    for(int i=0;i<n;i++)
        for(int j=g-w[i]; j>=0 ;j--)
        {
            if(optim[j+w[i]] < optim[j]+p[i])
            {
                optim[j+w[i]] = optim[j]+p[i];
                if(optim[j+w[i]] > sol)
                    sol = optim[j+w[i]];
            }
        }

    printf("%d",sol);
    return 0;
}