#include <iostream>
#include <fstream>
using namespace std;
 
ifstream f("rucsac.in");
ofstream g("rucsac.out");
 
int N, G, optim[10001], p[10001], w[10001], sol;
int main(){
    f>>N>>G;
    for (int i = 1; i<=N; ++i)
        f>>w[i]>>p[i];
    for (int i = 1; i<= N; ++i){
        for (int j = 0; j <= G-w[i]; ++j){
            if (optim[j+w[i]] < optim[j] + p[i])
                optim[j+w[i]] = optim[j] + p[i];
            if (optim[j+w[i]] > sol)
                sol = optim[j+w[i]];
        }
    }
    g<<sol;
}