#include <fstream>
#define GMAX 10004

using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");

int dp[GMAX][2];
int n, G, col, w, p, i, j;

int main()
{
 fin>>n>>G;
 fin>>w>>p;
 for (i=w; i<=G; i++)
     dp[i][0]=p;
 col=1;
 for (i=2; i<=n; i++)
     {
      fin>>w>>p;
      for (j=w; j <= G; j++)
          dp[j][col]=max(dp[j-w][1-col]+p, dp[j][1-col]);
      col=1-col;
     }
 fout<<dp[G][1-col];
 return 0;
}