#include<cstdio>
#include<algorithm>
using namespace std;
FILE*in=fopen("rucsac.in","r");
FILE*out=fopen("rucsac.out","w");
int n,g,i,j,w[5003],v[5003],m[10003];
int main()
{
    fscanf(in,"%d%d",&n,&g);
    for(i=1;i<=n;i++)
    {
        fscanf(in,"%d%d",&w[i],&v[i]);
    }
    for(j=1;j<=n;j++)
    {
        for(i=g;i>=1;i--)
        {
            if(i>=w[j])
            {
                m[i]=max(m[i],m[i-w[j]]+v[j]);
            }
        }
    }
    fprintf(out,"%d",m[g]);
}