#include<cstdio>
#include<cstdlib>
#include<iomanip>
#include<cmath>
#include<cstring>
using namespace std;
FILE *f=fopen("rucsac.in","r");
FILE *g=fopen("rucsac.out","w");
int gr[5001],pr[5001],a[1001],b[1001],n,G;
int main()
{
    int i,j;
    fscanf(f,"%d%d",&n,&G);
    for(i=1;i<=n;i++)
    {
        fscanf(f,"%d%d",&gr[i],&pr[i]);
    }

    for(i=1;i<=n;i++)
    {
        for(j=gr[i];j<=G;j++)
            b[j]=max(a[j],a[j-gr[i]]+pr[i]);
        memcpy(a,b,sizeof(b));
    }
    fprintf(g,"%d",b[G]);
    return 0;
}