/*#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

//ifstream f( "rucsac.in" );
//ofstream g( "rucsac.out" );

const int dim1 = 5005; /// nr de obiecte
const int dim2 = 10001; /// capacitatea maxima a Rucsacului.
int greut[ dim1 ], val[ dim1 ], R, dp[ dim2 ], n;
int maxim, poz_max; /// il folosesc sa tin minte cine este obiectul anterior folosit
vector<int> tata[ dim2 ];

/// Cu dedicatie, afisarea pentru Tudor si Dan
void afiseaza_dinamica( int nr_obiecte )
{
    cout << endl << "Dinamica pentru primele " << nr_obiecte << " obiecte." << endl;
    cout << "Folosesc: ";
    for( int i = 1; i <= nr_obiecte; ++i )
        cout << i << "(g: " << greut[ i ] << ", val: " << val[ i ] << ")  ";
    cout << endl;
    for( int i = 1; i <= R; ++i )
        cout << dp[ i ] << "  ";
    cout << endl;
    cout << "Obiectele folosite pentru toate capacitatile:" << endl;
    for( int i = 1; i <= R; ++i )
        {
            cout << "Capacitatea " << i << ", valoare " << dp[ i ] <<": ";
            for( int j = 0; j < tata[i].size(); ++j )
                cout << tata[ i ][ j ] << "  ";
            cout << endl;
        }
    cout << endl;

}

/// dp[ i ] = cea mai mare val pe care o pot obtine pentru un ruc
void rucsac_standard_valori_mici()
{
    int i, j, greut_ant; /// greutatea anterioara este greutatea la care adaug obiectul i
    for( i = 1; i <= n; ++i ) /// pentru fiecare obiect in parte
        {
            greut_ant = R - greut[ i ]; /// maximul posibil pentru o greutate anterioara
            cout <<"greutatea anterioara este : "<<greut_ant<<endl;
            for( j = greut_ant; j >= 0; --j ) /// ca sa nu oun de mai multe ori un acelasi obiect
                {
                    /// Pot folosi sau nu obiectul i. Daca il folosesc, la greutatea anterioara pusa in rucsac se adauga greutatea obiectului i. Suma este sigur <= R, deoarece plecam de la ea in jos
                    /// daca obtin o valoare mai buna decat era inainte, o retin. Altfel nu modific. De aceea e nevoie de un maxim.
                    /// cea mai buna valoare obtinuta pentru o greutate anterioara, j,  este dp[ j ], iar pentru greutatea noua, prin adaugarea obiectului i, este dp[ j + greut[i] ]
                    /// valoarea obtinuta prin adaugarea obiectului i, val[i], cu greutatea greut[j] este dp[ j ] + val[ i ].
                    /// Seamana cu monezile (coin change), ma uit in spate, de unde pot avea o suma mai buna.
                    /// Atentie, NU se reactualizeaza toate cele anterioare ci doar o parte
                    if( dp[ j ] + val[ i ]  >  dp[ j + greut[i] ] )
                        {
                            dp[ j + greut[i] ] = dp[ j ] + val[ i ];

                            if( dp[ j + greut[i] ]   >  maxim )
                                {
                                    maxim = dp[ j + greut[i] ];
                                    poz_max = i;
                                }

                            /// ATENTIE mai jos: este o abordare gresita!
                            if(tata[ i ].size()  >  0 )
                                tata[ i ].pop_back();
                            tata[ j + greut[i] ].push_back( i );
                        }
                }
            afiseaza_dinamica( i );
        }
}

int main()
{
    int i;
    cin >> n >> R;
    for( i = 1; i <= n; ++i )
        cin >> greut[ i ] >> val[ i ];

    rucsac_standard_valori_mici();

    cout << endl << endl;
    cout << "dp[ " << R << " ]  =  " << dp[ R ] << endl;
    cout << "Valoarea maximului: " << maxim << endl;



    return 0;
}


/**
Pe exemplul
6 10

3 7
3 4
1 2
1 9
2 4
1 5
Trebuie sa dea 1(3, 7), 2(3, 4), 5(2, 4), 6(1, 5).
**/

#include <fstream>
using namespace std;
ifstream cin( "rucsac.in" );
ofstream cout( "rucsac.out" );

const int dim1 = 5005; /// nr de obiecte
const int dim2 = 10001; /// capacitatea maxima a Rucsacului.
int greut[ dim1 ], val[ dim1 ], R, dp[ dim2 ], n;
int maxim, poz_max; /// il folosesc sa tin minte cine este obiectul anterior folosit
//vector<int> tata[ dim2 ];

/// Cu dedicatie, afisarea pentru Tudor si Dan

/// dp[ i ] = cea mai mare val pe care o pot obtine pentru un ruc
void rucsac_standard_valori_mici()
{
    int i, j, greut_ant; /// greutatea anterioara este greutatea la care adaug obiectul i
    for( i = 1; i <= n; ++i ) /// pentru fiecare obiect in parte
        {
            greut_ant = R - greut[ i ]; /// maximul posibil pentru o greutate anterioara
            //cout <<"greutatea anterioara este : "<<greut_ant<<endl;
            for( j = greut_ant; j >= 0; --j ) /// ca sa nu oun de mai multe ori un acelasi obiect
                {
                    if( dp[ j ] + val[ i ]  >  dp[ j + greut[i] ] )
                        {
                            dp[ j + greut[i] ] = dp[ j ] + val[ i ];

                            if( dp[ j + greut[i] ]   >  maxim )
                                {
                                    maxim = dp[ j + greut[i] ];
                                    poz_max = i;
                                }
                        }
                }
            //afiseaza_dinamica( i );
        }
}

int main()
{
    int i;
    cin >> n >> R;
    for( i = 1; i <= n; ++i )cin >> greut[ i ] >> val[ i ];
    rucsac_standard_valori_mici();
    cout << maxim;

    return 0;
}