//#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int d[5001][5001],w[5001],p[5001];
int main()
{
    int n,g,i,j;
    fin >> n >> g;
    for(i = 1; i <= n; i++)
        fin >> w[i] >> p[i];
   fin.close();
   for(i = 1; i <= n; i++)
   {
       for(j = 1; j <= g; j++)
        {
            d[i][j] = d[i-1][j];
            if(w[i]<=j)
              d[i][j] = max(d[i][j],d[i-1][j-w[i]]+p[i]);
        }
   }
    fout << d[n][g]<<"\n";
   fout.close();
    return 0;
}