#include <fstream>
using namespace std;

int N,G, W[5030], P[5030], dp[5000][10030]; bool l;

/*
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,j;
    for (i=1; i<=N; i++)
        in >> W[i] >> P[i];

    for (i=1; i<=N; i++){
        l=!l;
        for (j=0; j<=G; j++){

            dp[l][j]=dp[!l][j];
            if (W[i]<=j)
                dp[l][j]=max(dp[!l][j],dp[!l][j-W[i]]+P[i]);
        }
    }
    out << dp[l][G];
    return 0;
}