#include<stdio.h>
int n, i, j, g, w[5001], v[5001], a[10001], s;
int main(){
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    scanf("%d %d", &n, &g);
    for(i=1; i<=n; i++)
        scanf("%d %d", &w[i], &v[i]);
    for(i=1; i<=n; i++)
        for(j=g-w[i]; j>=0; j--)
            if(a[ j+w[i] ]<a[j]+v[i])
            {
                a[ j+w[i] ]=a[j]+v[i];
                if(a[ j+w[i] ]>s)
                    s=a[ j+w[i] ];
            }
    printf("%d\n", s);
}