#include <iostream>
#include <fstream>

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