#include <fstream>
#include <vector>
using namespace std;

struct obiect
{
    int greutate, valoare;
};

int main()
{
    int numar_obiecte, greutate_maxima;
    obiect *vector_obiecte;
    numar_obiecte = greutate_maxima = 0;
    ifstream f("rucsac.in");
    f>>numar_obiecte>>greutate_maxima;
    vector_obiecte = new obiect[numar_obiecte];
    for (int i=0; i<numar_obiecte; ++i)
        f>>vector_obiecte[i].greutate>>vector_obiecte[i].valoare;
    f.close();

    int **matrice_valori;
    matrice_valori = new int*[numar_obiecte + 1];
    for(int i=0; i<numar_obiecte + 1; ++i)
        matrice_valori[i] = new int[greutate_maxima + 1];
    for(int i=0; i<=greutate_maxima; ++i)
        matrice_valori[0][i] = 0;

    for(int i=1; i<=numar_obiecte; ++i) //pt fiecare obiect
        for(int j=0; j<=greutate_maxima; ++j) //pt fiecare greutate posibila
        {
            if(j>=vector_obiecte[i-1].greutate) //putem sa adaugam obiectul?
                matrice_valori[i][j] = max(matrice_valori[i-1][j], matrice_valori[i-1][j - vector_obiecte[i-1].greutate] + vector_obiecte[i-1].valoare); //incercam sa aduaguam alegand dintre valoarea dinainte si cea cu adaugarea obiectului curent
            else
                matrice_valori[i][j] = matrice_valori[i-1][j]; //nu, folosim val veche
        }

    ofstream g("rucsac.out");
    g<<matrice_valori[numar_obiecte][greutate_maxima]; //greutatea maxima dupa ce toate val au fost procesate
    g.close();

    return 0;
}