#include <iostream>
#include <fstream>

using namespace std;

int n, g, profit[5001], greutate[5001], P[5001][10001];

void Citire()
{
    ifstream f("rucsac.in");

    f >> n >> g;

    for(int i = 1; i <= n; i++)
        f >> greutate[i] >> profit[i];
}

void FormareDP()
{
    for(int obiect = 1; obiect <= n; obiect++)
        for(int G_rucsac = 1; G_rucsac <= g; G_rucsac++)
        {
            if(greutate[obiect] > G_rucsac)
                P[obiect][G_rucsac] = P[obiect - 1][G_rucsac];
            else
                P[obiect][G_rucsac] = max(profit[obiect] + P[obiect - 1][G_rucsac - greutate[obiect]], P[obiect - 1][G_rucsac]);
        }
}

void Afisare()
{
    ofstream g("rucsac.out");
    g << P[n][g];
}

int main()
{
    Citire();
    FormareDP();
    Afisare();

    return 0;
}