#include<iostream>
using namespace std;
#include<stdio.h>
FILE *f,*d;
int c[5001],g[5001],cmax[10001],uz[10001][5001],i,n,gmax,cost,s,maxim;
int main()
{
    f=fopen("rucsac.in","r");
    d=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(s=1;s<=gmax;s++)
        for(i=1;i<=n;i++)
        if(g[i]<=s&&cmax[s-g[i]]!=-1&&uz[s-g[i]][i]==0)
          if(cmax[s]<c[i]+cmax[s-g[i]])
    {

        cmax[s]=c[i]+cmax[s-g[i]];
        for(int k=1;k<=n;k++)
            uz[s][k]=uz[s-g[i]][k];
        uz[s][i]=1;
    }

        for(i=1;i<=gmax;i++)
            if(cmax[i]>maxim)
            maxim=cmax[i];
       fprintf(d,"%d",maxim);



}