#include <cstdio>

using namespace std;

int i,SOL,j,n,g;
int w[5005], p[5005], s[10005];

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], &p[i]);

    s[0]=0;
    SOL=0;

    for(i=1; i<=n; i++)
        for(j=g-w[i]; j>=0; j--)

            if ( s[j+w[i]]< s[j]+ p[i] )
            {
                s[j+w[i]]=s[j]+p[i];

                if ( s[j+w[i]]>SOL )
                    SOL=s[j+w[i]];

            }

    printf ("%d\n", SOL);



    return 0;
}