#include <cstdio>

using namespace std;

int n,gmax,g[5001],c[5001],cmax[10002],util[10005][5005];
int maxx;
int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    scanf("%d%d",&n,&gmax);
    for(int i=1;i<=n;i++)
       scanf("%d%d",&g[i],&c[i]);
    for(int i=1;i<=gmax;i++)
        cmax[i]=-1;
    for(int i=1;i<=n;i++)
       for(int j=gmax-g[i];j>=0;j--)
           if(cmax[j]!=-1)
             if(cmax[j]+c[i]>cmax[j+g[i]])
                 {cmax[j+g[i]]=c[i]+cmax[j];
                 for(int k=1;k<=n;k++)
                    util[j+g[i]][k]=util[j][k];
                 util[j+g[i]][i]=1;
                 }
    int k;
    for(int i=1;i<=gmax;i++)
       if(cmax[i]>maxx) {maxx=cmax[i];k=i;}
    printf("%d\n",maxx);
   // for(int i=1;i<=n;i++)
    //   if(util[k][i])printf("%d ",i);
    return 0;
}