/// note!
/// ce este scris cu /// e adaugat de mine (ma refer la comentarii
/// pentru a obtine mai multe puncte vom incerca sa reducem spatiul utilizat
/// observam ca pentru a face algoritmul noi la un moment dat nu ne folosim decat de coloana i-1 pentru a construi coloana i

/// tactica:
/*
    -vom declara 2 vectori: a[10010], b[10010]
    -vom declara 2 pointeri pe care ii folosim pentru a ne referii la cei 2 vectori: *old_line, *new_line

    -fie a este randul pentru 0 obiecte si b este noul rand

    -memoram in new_line adresa de la vectorul b: new_line = b;
                                                 old_line = a;

    -acuma old_line[i] este greutatea i din randul vechi
    -si new_line[i] este greutatea i din randul pe care il construim

    -dupa ce executam algoritmul pentru construirea randului schimbam cei 2 vectori intre ei
    (new_line devine old_line si in loopul urmator modivicam noul new_line):      swap(new_line, old_line);

    -asa reducem memoria de la intreaga matrice la doar doi vectori

*/


#include <fstream>
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
using namespace std;
//int G[50], V[50];//greutatea si castigul fiecarui obiect

//int D[100][1000];

/// nu mai folosim D
/// acum declaram a, b, *new_line, *old_line;
int a[10010], b[10010], *new_line, *old_line;
///fiind declarati global, a si b sunt declarati din start cu 0 pe toate pozitiile

//D[i][j] cel mai bun castig pentru primele i obiecte avand greutatea insumata j
struct obiect
{
    int G;
    int V;
};
int main()
{
    int n,GMax,C;
    obiect ob[1000]; ///am schimbat denumirea vectorului de obiecte din a in ob
    fin>>n>>GMax;
    for (int i = 1; i <= n; i++) /// citim obiectele
        fin>>ob[i].G>>ob[i].V;

    /// nu mai avem nevoie de aceasta initializare pt D
    /*
    for( int j = GMax; j >= 0;j--)
    D[0][j]=0;
    for( int i = 1; i <= n; i++)
    D[i][0]=0;
    */

    /// setam pointerii sa indice spre adresele celor 2 vectori:
    old_line = a;
    new_line = b;

    for( int i = 1; i <= n; i++){
        for( int j =0; j <= GMax; j++){
            if(ob[i].G>j)
                new_line[j] = old_line[j]; /// modificam in randul noii linii
            else if( old_line[j] < old_line[j-ob[i].G] + ob[i].V ) /// D[i-1][ .. ] devine old_line, D[i][ ... ] este new_line
                new_line[j] =old_line[j-ob[i].G] + ob[i].V;//adaug obiectul i
            else
                new_line[j]=old_line[j];//nu adaug obiectul i
        }
        /// odata ce am completat randul, interschimb cei 2 pointeri:
        swap(new_line, old_line);
    }

    /// la final, rezultatul apare pe pointerul old_line
    C = old_line[GMax];
    fout<<C;
    return 0;
}