#include <iostream>
#include <fstream>

using namespace std;

int n, g, dp[10000];
int w[5000], p[5000];
void dinamica(){
    for (int i = 0; i < n; ++i) {
        for(int wi = g ; wi >= w[i]; --wi){
            dp[wi] = max(dp[wi - w[i]] + p[i], dp[wi]);
        }
    }
}

int main() {
    ifstream f("rucsac.in");
    ofstream o("rucsac.out");
    f>>n>>g;
    for (int i = 0; i < n; ++i) {
        f>>w[i]>>p[i];
    }
    dinamica();
    o<<dp[g];
    return 0;
}