#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][5003];
int main()
{
    fscanf(in,"%d%d",&n,&g);
    for(i=1;i<=n;i++)
    {
        fscanf(in,"%d%d",&w[i],&v[i]);
    }
    for(i=1;i<=g;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(i>=w[j])
            {
                m[i][j]=max(m[i][j-1],m[i-w[j]][j-1]+v[j]);
            }
            else
            {
                m[i][j]=m[i][j-1];
            }
        }
    }
    fprintf(out,"%d",m[g][n]);
}