#include <fstream>
#define nmax 5001
#define gmax 10001
using namespace std;
ifstream is ("rucsac.in");
ofstream os ("rucsac.out");

struct O{
    int w, v;
}Obj[nmax];

int N, G, ANS[gmax], ANSW;

int main()
{
    int x, y;
    is >> N >> G;
    for(int i = 1; i <= N; ++i)
    {
        is >> x >> y;
        Obj[i].w = x, Obj[i].v = y;
    }

    for(int i = 1; i <= N; ++i)
        for(int j = G - Obj[i].w; j >= 0; --j)
            if(ANS[j + Obj[i].w] < ANS[j] + Obj[i].v)
            {
                ANS[j + Obj[i].w] = ANS[j] + Obj[i].v;
                ANSW = max(ANSW, ANS[j + Obj[i].w]);
            }
    os << ANSW;

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