#include <iostream>
#include <fstream>
#define nmax 10005
using namespace std;

int n, g, w, p, a[nmax], b[nmax];
int *first =a, *second =b, *aux;

int main()
{
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");

    fin >> n >> g;

    for(int j=0; j<=g; j++)
    {
        *(first+j) = 0;
     }

    for(int i=1; i<=n; i++)
    {
        fin >> w >> p;
        for(int j=0; j<=g; j++)
        {
            if (j-w <0) *(second+j) = *(first+j);
                  else  *(second+j) = max( *(first+j-w)+p, *(first+j) );
        }
        aux = first;
        first = second;
        second = aux;
    }

    fout << *(second + g);
    fin.close();
    fout.close();
    return 0;
}