// Knapsack - varianta(0 - 1)
//          - varianta discreta

// se da un rucsac de capacitate C si n obiecte
// pt fiecare obiect se cunoaste greutatea lui si valoarea lui
//fiecare obicet e unic
// valoarea maxima a obiectelor care puse in rucsac a. i. greutatea obiectelor
// alese sa nu depaseasca G

#include <fstream>

using namespace std;

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


const int MaxN = 5001;
const int MaxG = 10001;

int g[MaxN], v[MaxN];
int n, G;
int c[MaxN][MaxG];
int a, b;
int t[MaxN][MaxG];

void Read();
void Knapsack_2D();

int main()
{

    Read();
    Knapsack_2D();
    os << c[n][G];
    is.close();
    os.close();
    return 0;
}

void Read()
{
    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];
            t[i][j] = t[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];
                t[i][j] = g[i];
            }

        }
    }
}






/*
Starea problemei: C, n, G
Stare intermediara: C, i = pozitie in sirul de obiecte, j=greutatea maxima care o pot avea obiectele alese:
                                int c[maxN][maxG]
                    c[i][j] = val max a unor obiecte dintre intervalul 1->i a caror greutate
                              sa nu depaseasca j

c[i - 1][j] - > c[i][j] daca i nu se pune in rucsac
c[i - 1][j - g[i]] -> c[i][j] daca i se pune in rucsac

*/