#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

const int NMAX = 5001;
const int INFI = 0x3f3f3f3f;
int Gmax, N;
int g[NMAX], p[NMAX];
int memo[NMAX][2 * NMAX];

int rucsac(int i, int Gramas){
    if(i == 0){
        return 0;
    }

    if(memo[i][Gramas] != INFI){
        return memo[i][Gramas];
    }

    int profit_skip_obj = rucsac(i - 1, Gramas);

    int profit_luat_obj = 0;
    if(g[i] <= Gramas){
        profit_luat_obj = p[i] + rucsac(i - 1, Gramas - g[i]);
    }

    int ans;
    if(profit_skip_obj > profit_luat_obj){
        ans = profit_skip_obj;
    }else{
        ans = profit_luat_obj;
    }
    memo[i][Gramas] = ans;
    return memo[i][Gramas];
}



int main()
{
    fin >> N >> Gmax;
    for(int i = 1; i <= N; i++){
        fin >> g[i] >> p[i];
    }
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= Gmax; j++){
            memo[i][j] = INFI;
        }
    }
    fout << rucsac(N, Gmax);
    return 0;
}