#include <iostream>
#include <fstream>

using namespace std;

int n, g, profit[5001], greutate[5001], P[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 = g; G_rucsac >= greutate[obiect]; G_rucsac--)
            P[G_rucsac] = max(P[G_rucsac], profit[obiect] + P[G_rucsac - greutate[obiect]]);
}

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

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

    return 0;
}