#include <iostream>
#include <cstdio>
#include <queue>
#define nmax 5003
using namespace std;

int n,g;
int w[nmax], p[nmax];
int sol[2*nmax];
int maxim;

int main()
{
    int i,j;
    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]);
    for(i=1;i<=n;i++)
    {
       for(j=g-w[i];j>=0;j--)
            if(sol[j+w[i]]< sol[j]+p[i])
            {
                sol[j+w[i]]=sol[j]+p[i];
                if(sol[j+w[i]]>maxim) maxim=sol[j+w[i]];
            }
    }
    cout<<maxim<<'\n';
    fclose(stdin);
    fclose(stdout);
    return 0;
}