#include <bits/stdc++.h>
#define nmax 5002
#define gmax 10002
using namespace std;
int w[nmax], p[nmax];
int optim[gmax];

int main()
{
    ifstream f("rucsac.in");
    ofstream fout("rucsac.out");
    int i, n, j, g;
    f >> n >> g;
    for (i=1; i<=n; ++i)
        f >> w[i] >> p[i];


    int sol=0;

    for (i=1; i<=n; ++i)
      for (j=g - w[i]; j >=0; --j)
      {
        if (optim[j+w[i]] < optim[j] + p[i])
        {
        optim[j+w[i]] = optim[j] + p[i];
        if (optim[j+w[i]] > sol)
            sol=optim[j+w[i]];
        }
      }
      fout << sol;


    return 0;

}