/*knapsack 0-1 / varianta discreta

    G, n               G capacitatea rucsacului
                        n nr de obiecte
    g[1]....g[n];  \
                    fiecare obiect este unic
    v[1].....v[n]; /


    se cere valoarea maxima a obiectelor care pot fi puse
            in rucsac astfel incat
                greutatea totala sa nu depaseasca G
                !! rucsacul poate sa nu fie plin



    Starea finala:
        C, n, G

    Starea generala / intermediara:
        C, i, j  => C = valoarea maxima luata din primele i
                            care au in total greutatea j

    c[i][j] = c[i-1][j] daca obiectul i nu se pune in rucsac
    altfel
    c[i][j] = c[i-1][j-g[i]] + v[i] daca obiectul i se pune in rucsac

*/
#include <fstream>
using namespace std;

ifstream is("rucsac.in");
ofstream os("rucsac.out");

int c[5000][10000]; //c[i][j] = vmax a unor obiecte din interv 1, i
                 // a caror greutate toala sa nu depaseasca j

int n, G, v[100], g[100];

void ReaD();
void Knapsack_2D();

int main()
{
    ReaD();
    Knapsack_2D();

    os << c[n][G];

    is.close();
    os.close();
    return 0;
}

void ReaD()
{
    int a, b;
    is >> n >> G;
    for( int i = 1; i <= n; ++i )
    {
        is >> a >> b;
        g[i] = a;
        v[i] = b;
    }
}

void Knapsack_2D()
{
    for( int i = 1; i <= n; ++i )
        for( int j = 1; j <= G; ++j )
        {
            c[i][j] = c[i-1][j];
            if( j >= g[i] && c[i][j] < c[i-1][j-g[i]] + v[i] )
                c[i][j] = c[i-1][j-g[i]] + v[i];
        }





}