#include <cstdio>
#include <vector>
using namespace std;
int i,j,k,l,m,n,max1,x,y,g1,g[5000],v[5000],prins[5000][5000],gr[5000],vr[5000],hot,ruc,greutatea;
void rucsacfraier()
{
for(i=0;i<g1+1;i++)
 {
    for(j=1;j<n+1;j++)
        if(i-g[j]>=0) {  if(prins[i-g[j]][j]==0) {
                              if(vr[i-g[j]]+v[j]>vr[i]) {vr[i]=vr[i-g[j]]+v[j]; gr[i]=gr[i-g[j]]+g[j];ruc=i-g[j];hot=j;}
                              if(vr[i-g[j]]+v[j]==vr[i]) if(gr[i-g[j]]+g[j]<gr[j]) {gr[i]=gr[i-g[j]]+g[j];ruc=i-g[j];hot=j; }}
                        if(prins[i-g[j]][j]==1){
                              if(vr[i-g[j]]>vr[i]) {vr[i]=vr[i-g[j]]; gr[i]=gr[i-g[j]];ruc=i-g[j];}
                              if(vr[i-g[j]]==vr[i]) if(gr[i-g[j]]<gr[j]) {gr[i]=gr[i-g[j]];ruc=i-g[j]; }}
                     }
    for(j=1;j<n+1;j++)
      prins[i][j]=prins[ruc][j];
      if(hot!=0)
          prins[i][hot]=1;
 }
}

int main()
{
   freopen("rucsac.in","r",stdin);
   freopen("rucsac.out","w",stdout);
    scanf("%d %d",&n,&g1);
    for(i=1;i<n+1;i++)
      scanf("%d %d",&g[i],&v[i]);
    rucsacfraier();
    printf("%d",vr[g1]);
    return 0;
}