#include <fstream>
using namespace std;

int N,G, W[5030], P[5030], dp[5030][10030]; bool viz[5030][10030];
void solve(int item, int weight){
    if(item==0 || weight==0 || viz[item][weight])
        return;
    viz[item][weight]=1;

    solve(item-1,weight);
    if (W[item]<=weight)
        solve(item-1,weight-W[item]);

    dp[item][weight]=dp[item-1][weight];
    if (W[item]<=weight)
        dp[item][weight]=max(dp[item][weight],dp[item-1][weight-W[item]]+P[item]);
}
int main(){
    ifstream in("rucsac.in");
    ofstream out("rucsac.out");
    in >> N >> G;

    int i;
    for (i=1; i<=N; i++)
        in >> W[i] >> P[i];

    solve(N,G);

    out << dp[N][G];
    return 0;
}