#include <cstdio>

using namespace std;

int g[5001],cmax[10001],ok[5001][5001],i,n,gmax,j,k,poz,c[5001];

int main()
{
    FILE *f=fopen("rucsac.in","r");
    FILE *gr=fopen("rucsac.out","w");
    fscanf(f,"%d %d",&n,&gmax);
    for(i=1;i<=n;i++) fscanf(f,"%d %d",&g[i],&c[i]);
    for(i=1;i<=gmax;i++)cmax[i]=-1;
    for(i=1;i<=gmax;i++)
    for(j=1;j<=n;j++)
    if(g[j]<=i&&cmax[i-g[j]]!=-1&&ok[i-g[j]][j]==0)
    if(cmax[i]<cmax[i-g[j]]+c[j])
    {
        cmax[i]=cmax[i-g[j]]+c[j];
        for(k=1;k<=n;k++)ok[i][k]=ok[i-g[j]][k];
        ok[i][j]=1;
    }
    poz=0;
    for(i=1;i<=gmax;i++)if(cmax[i]>poz)poz=cmax[i];
    fprintf(gr,"%d",poz);
    fclose(f);
    fclose(gr);
    return 0;
}