#include <iostream>
#include <fstream>
#define dimg 10005
#define dimn 5005

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

int N, G;
int line[dimg];
int val[dimn], w[dimn];

void citire() {
    f >> N >> G;
    for (int i=0; i<N; i++)
        f >> w[i+1] >> val[i+1];
}
void rezolvare() {
    int max = 0;
    for (int i=1, j; i<=N; i++)
        for (j = G; j>=w[i]; j--)
            if(line[j] < line[j-w[i]] + val[i]) {
                line[j] = line[j-w[i]] + val[i];
                max = std::max (max, line[j]);
            }
    g << max;
}

int main()
{
    citire();
    rezolvare();

    return 0;
}