#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n, w, m[5001],c[5001], V[2][5001];
int main()
{
   f>>n>>w;
   for(int i=1;i<=n;i++)
    {f>>m[i]>>c[i];}
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=w;j++)
    {
      if(j<m[i]) V[1][j]=V[0][j];
      else V[1][j]=max(V[0][j],V[0][j-m[i]]+c[i]);
    }
   for(int j=1;j<=w;j++)
   {
    V[0][j]=V[1][j]; V[1][j]=0;
   }
}
 g<<V[0][w];
    return 0;
}