#include <fstream>
using namespace std;
int d[10002];
int v[5002], p[5002];

int n, suma, indiceMaximUnu, i, j, G, st, sol;
int main () {
    ifstream fin ("rucsac.in");
    ofstream fout("rucsac.out");
/// d[i] = profitul maxim sa incarc in rucsac cantitatea i
    fin>>n>>G;
    for (i=1;i<=n;i++) {
        fin>>v[i]>>p[i];
    }


    d[0] = 0; /// profitul maxim sa incarc in rucsac greutate 0 este 0.
    /// d[celelalte] = -1 (marcaj)
    for (i=1;i<=G;i++)
        d[i] = -1;

    indiceMaximUnu = 0;
    for (i=1;i<=n;i++) {
        /// am ajuns la v[i] si facem sume luandu-l in calcul si pe el
        for (j=indiceMaximUnu;j>=0;j--)
            if (d[j] != -1) /// sa obtinuse anterior suma de greuitati j
                if (j+v[i] <= G) {
                    if (  d[j+v[i]] < d[j] + p[i] ) {
                        d[ j+v[i] ] = d[j] + p[i];
                        indiceMaximUnu = max(indiceMaximUnu, j+v[i]);
                    }
                }
    }
    for (i=1;i<=G;i++)
        sol = max (sol, d[i]);
    fout<<sol;
    return 0;
}

/**
Programare dinamica

Problema rucsacului.
Ai un rucsac de greutate G.
Ai n obiecte, fiecare de o greutate cunoscuta v[i] si trebuie sa incarcam
cat mai bine rucsacul cu obiecte (sa incarc o greutate maxima <= G)
- un obiect nu poate fi taiat (ori il iau ori nu)

Iau elementele la rand (nu neaparat sortat)
Cand ajung la un element trebuie sa stiu toate sumele care se pot obtine cu cele
analizate deja inaintea lui.
Dupa ce il iau si pe el in calcul obtin sume noi inainte de a trece la urmatorul
element
G = 17

3 5 2 9 1 11


0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
1 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0

Iau pe 3:
cu el obtin suma 3.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
0 0 1 0 0 0 0 0 0  0  0  0  0  0  0  0  0


Iau pe 5:
Obtin suma 3, 5, 8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
0 0 1 0 1 0 0 1 0  0  0  0  0  0  0  0  0



Iau pe 2:
3, 5, 8, 2, 7, 10
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
1 0 1 1 0 1 0 1 1 0  1  0  0  0  0  0  0  0

for (i=1;i<=n;i++) {
    /// am ajuns la v[i] si facem sume luandu-l in calcul si pe el
    for (j=G;j>=0;j--)
        if (d[j] == 1)
            if (j+v[i] <= G)
                d[ j+v[i] ] = 1;
}

Urmeaza 9


Folosesc un vector de frecventa in care sumele sunt indici si in care
marchez cu 1 in dreptul sumelor obtinute


Iau pe 9:



G = 11
1 2 6 7

1 2 6


28
7
11
8
9
7
27

7 9 11 7 27 28 8
0 0  1 1  0  1 0

{7, 9, 27, 8}
{11, 7, 8}

**/