#include <iostream>

using namespace std;
struct obiect{
    int g,p;
}v[5001];
int dp[5001][10001];
int main(int argc, const char * argv[]) {
    int n,G,i,j;
    cin >> n >> G;
    for(i = 1 ; i <= n ; ++i){
        cin >> v[i].g >> v[i].p;
    }
    for(i = 1 ; i <= n ; ++i){
        for(j = 0 ; j <= G ; ++j){
            dp[i][j] = dp[i - 1][j];
            
            if (j >= v[i].g)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i].g] + v[i].p);
        }
    }
    
    cout << dp[n][G] << '\n';
    return 0;
}