#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

int n,g, w[5004], p[5004];
long long dp[2][10004];


int main()
{
    cin>>n>>g;

for(int j=1; j<=n; ++j){
    int o, t;
    o = j%2; t = (j-1)%2;
    cin>>w[j]>>p[j];
        for(int i=1; i<=g; ++i){
            dp[o][i] = dp[t][i];
            if(w[j]<=i) dp[o][i] = max(dp[o][i],dp[t][i-w[j]]+p[j]);

        }

}
    cout<<dp[n%2][g];


    return 0;
}