#include<cstdio>
using namespace std;
int W[5001],P[5001],Optim[10001];
int i,n,j,g,sol;
int main()
    {
        freopen("rucsac.in","r",stdin);
        freopen("rucsac.out","w",stdout);
        scanf("%d%d",&n,&g);

        Optim[0] = 0;

        for(i=1;i<=n;i++)
            scanf("%d%d",&W[i],&P[i]);
        for( i = 1; i <= n; ++i)
            for( 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);

    }