#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;
 for (i=1; i<=n; i++)
     {
      fin>>w>>p;
      for (j=0; j <= G; j++)
          if (j-w >= 0)
             dp[j][col]=max(dp[j-w][1-col]+p, dp[j][1-col]);
             else
             dp[j][col]=dp[j][1-col];

      col=1-col;
     }
 fout<<dp[G][1-col];
 return 0;
}