#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+1], greutate[nrObiecte+1];

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

    }

    int capacitati[capacitateRucsac+1];

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

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

    g<<capacitati[capacitateRucsac];
    /*
    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;
}