#include <iostream>
#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n, G, profit[5001], greutate[5001], P[10001];
int main() {
    f >> n >> G;
    for(int i = 1; i <= n; i++)
        f >> greutate[i] >> profit[i];
    for(int i = 1; i <= n; i++)
        for(int j = G; j >= greutate[i]; j--)
            P[j] = max(P[j], profit[i] + P[j - greutate[i]]);
    g << P[G];
    return 0;
}