#include <iostream>
#include <fstream>
#define maxn 5005
#define maxg 10010
using namespace std;

int max(int x,int y)
{if(x>y)
return x;
return y;
}

int main()


{int n,g,i,j,d[2][maxg],x,y,w[maxg],p[maxg];
fstream f("rucsac.in",ios::in);
fstream h("rucsac.out",ios::out);
f>>n>>g;

    d[0][0]=0;d[1][0]=0;
for(i=0;i<=g;i++)
    d[0][i]=0;

for(i=1;i<=n;i++)
f>>w[i]>>p[i];


for(i=1;i<=n;i++)
   {for(j=0;j<=g;j++)
{ d[1][j]=d[0][j];

if(w[i]<=j)
d[1][j]=max(d[1][j],d[0][j-w[i]]+p[i]);

}
 for(x=0;x<=g;x++)
        d[0][x]=d[1][x];

   }

 h<<d[1][g];


f.close();
h.close();




}