#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX = 5000 + 1;
const int GMAX = 10000;

int gmax, n, minim, suma;
int greutate[NMAX], profit[NMAX];
int sol[GMAX];

void citeste() {
    f >> n >> gmax;
    minim = GMAX + 1;
    for (int i = 1; i <= n; i++) {
        f >> greutate[i] >> profit[i];
        suma += greutate[i];
        minim = min(greutate[i], minim);
    }
}

void rezolva() {
    for (int i = 1; i <= n; i++) {
        for (int g = gmax; g >= 1; g--)
            if (greutate[i] <= g)
                sol[g] = max(sol[g], sol[g - greutate[i]] + profit[i]);
    }
}

int main() {
    citeste();
    rezolva();
    g << sol[gmax] << '\n';
    return 0;
}