#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;

int profit[5001][10001]; short int n, g[5001],G,c[10001];
ofstream out("rucsac.out");

void citeste()
{ ifstream f("rucsac.in");
  f>>n>>G;
  int i;
  for(i=1;i<=n;i++)
    f>>g[i]>>c[i];
}
void calculprofit()
{ int i,j,x;
  for(i=1;i<=n;i++)
     for(j=1;j<=G;j++)
     { if(j>=g[i])
          profit[i][j]=max(profit[i-1][j-g[i]]+c[i], profit[i-1][j]);
       else
          profit[i][j]=profit[i-1][j];
     }
}

int main()
{   citeste();
    calculprofit();
    out<<profit[n][G]<<endl;
    return 0;
}