//#include <iostream>
#include <fstream>

using namespace std;

int n, g;
int w[5001], p[5001];
int lcrt[10001], lprec[10001];

void citire()
{
    ifstream fin("rucsac.in");
    fin >> n >> g;
    for(int i = 1; i <= n; i++)
        fin >> w[i] >> p[i];
}

int rezolvare()
{
    for(int i = 1; i <= n; i++)
    {
        for(int cw = 0; cw <= g; cw++)
        {
            lcrt[cw] = lprec[cw];
            if(cw >= w[i])
                lcrt[cw] = max(lcrt[cw], lprec[cw-w[i]] + p[i]);
        }
        for(int cw = 0; cw <= g; cw++)
        {
            lprec[cw] = lcrt[cw];
        }
    }
    return lcrt[g];
}

void afisare()
{
    ofstream fout("rucsac.out");
    fout << rezolvare();
}

int main()
{
    citire();
    afisare();
    return 0;
}