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