#include <fstream>
#include <iostream>

using namespace std;

const int NMAX = 5000;
const int GMAX = 10000;

struct ura {
    int g;
    int p;
};
ura v[NMAX + 1];

int dp[2][GMAX + 1]; /// dp[i][j] = max( dp[i - 1][j], p + dp[i - 1][j - p] );

static inline void copiere( int g ) {
    int i;
    for ( i = 0; i <= g; i ++ )
        dp[0][i] = dp[1][i];
}

int main() {
    ifstream fin( "rucsac.in" );
    ofstream fout( "rucsac.out" );
    int n, i, g, j;
    fin >> n >> g;
    for ( i = 1; i <= n; i ++ ) {
        fin >> v[i].g >> v[i].p;
    }
    for ( i = 1; i <= n; i ++ ) {
            ///cout << i;
        for ( j = 1; j <= g; j ++ )
            dp[1][j] = ( j - v[i].g >= 0 ) ? max( dp[0][j], v[i].p + dp[0][j - v[i].g] ) : dp[0][j];
        copiere( g );
    }
    fout << dp[1][g];
    return 0;
}