#include <iostream>
#include <fstream>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");


int main()
{
    int nrObiecte, capacitateRucsac;
    f>>nrObiecte>>capacitateRucsac;

    int pret[nrObiecte], greutate[nrObiecte];

    for(int i=1;i<=nrObiecte;i++){
        f>> greutate[i]>>pret[i];

    }
    int capacitati[nrObiecte+1][capacitateRucsac+1];


    for(int obiect = 0; obiect <= nrObiecte; obiect++ )
         capacitati[obiect][0] = 0;
    for(int weight = 0; weight <= capacitateRucsac; weight++)
        capacitati[0][weight] = 0;

    for(int obiect = 1; obiect <= nrObiecte; obiect++ )
        for(int weight = 0; weight <= capacitateRucsac; weight++)
            if(greutate[obiect] <= weight)
                capacitati[obiect][weight] = max(capacitati[obiect-1][weight],
                                                 capacitati[obiect-1][weight - greutate[obiect]] + pret[obiect]);
            else
                 capacitati[obiect][weight] = capacitati[obiect-1][weight];

     g<<capacitati[nrObiecte][capacitateRucsac];

    return 0;
}