#include<iostream>
#include<fstream>
using namespace std;
const int NMAX=5000, GMAX=10000;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int w[NMAX+1], P[NMAX+1];
int d[2][GMAX+1];
int main()
{
    int n,g;
    fin>>n>>g;
    for(int i=1; i<=n; i++)
        fin>>w[i]>>P[i];
    int p=0,u=1;
    for(int i=1; i<=n; i++)
      {
          for(int cw=0; cw<=g; cw++)
        {
            d[u][cw]=d[p][cw];
            if(w[i]<=cw)
                d[u][cw]=max(d[u][cw],d[p][cw-w[i]]+P[i]);
        }
        swap(p,u);
      }

    fout<<d[p][g];

    fin.close();
    fout.close();
    return 0;
}