#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

const char infile[] = "rucsac.in";
const char outfile[] = "rucsac.out";

ifstream cin(infile);
ofstream cout(outfile);

const int MAXN = 5005;
const int MAXG = 10005;
const int oo = 0x3f3f3f3f;

typedef vector<int> Graph[MAXN];
typedef vector<int> :: iterator It;

const inline int min(const int &a, const int &b) { if( a > b ) return b;   return a; }
const inline int max(const int &a, const int &b) { if( a < b ) return b;   return a; }
const inline void Get_min(int &a, const int b)    { if( a > b ) a = b; }
const inline void Get_max(int &a, const int b)    { if( a < b ) a = b; }

int N, G, g[MAXN], c[MAXN], dp[2][MAXG], Ans = -1;

int main() {
    cin >> N >> G;
    for(int i = 1 ; i <= N ; ++ i)
        cin >> g[i] >> c[i];
    for(int i = 1 ; i <= N ; ++ i)
        for(int j = 1 ; j <= G ; ++ j) {
            dp[i&1][j] = dp[(i&1)^1][j];
            if(j >= g[i] && dp[i&1][j] < dp[(i&1)^1][j - g[i]] + c[i])
                dp[i&1][j] = dp[(i&1)^1][j - g[i]] + c[i];
        }
    cout << dp[N&1][G] << '\n';
    cin.close();
    cout.close();
    return 0;
}