#include <fstream>

using namespace std;

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

int W[5005];
int P[5005];
int dp[10005];

int main() {
    int n, g;
    cin>>n>>g;
    for (int i=1; i<=n; i++){
        cin>>W[i]>>P[i];
    }
    for (int i=1; i<=n; i++){
        for (int j=g - W[i]; j>=0; j--){
            dp[j + W[i]] = max(dp[j + W[i]] , dp[j] + P[i]);
        }
    }
    int ans = 0;
    for (int i=1; i<=g; i++){
        ans = max(ans, dp[i]);
    }
    cout<<ans;
    return 0;
}