#include<stdio.h>
#include<algorithm>
using namespace std;
int N,G,w[5001],p[5001],s[10001],x=0;
int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    scanf("%d%d",&N,&G);
    for(int i=1;i<=N;++i)
        scanf("%d%d",&w[i],&p[i]);

    s[0]=0;

    for(int i=1;i<=N;++i)
        for(int 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]]>x)
                    x=s[j+w[i]];
            }
    printf("%d",x);
    return 0;
}