#include <fstream>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
const int MAX_N = 5001;
const int MAX_G = 10000;
struct t_object{
    int gr;
    int pr;
};
int memo[MAX_N][MAX_G];
int dp_profit(int i, int C, t_object objs[]){
    if(i == 0)
        return 0;
    if(C == 0)
        return 0;
    if(memo[i][C] != 0)
        return memo[i][C];
    if(objs[i].gr > C){
        memo[i][C] = dp_profit(i - 1, C, objs);
        return memo[i][C];
    }
    int profit1 = dp_profit(i - 1, C, objs);
    int profit2 = objs[i].pr + dp_profit(i - 1, C - objs[i].gr, objs);
    memo[i][C] = max(profit1, profit2);
    return memo[i][C];
}
int main()
{
    int N, G;
    t_object objs[MAX_N];
    fin >> N >> G;
    for(int i = 1; i <= N; i++)
        fin >> objs[i].gr >> objs[i].pr;
    fout << dp_profit(N, G, objs);
    return 0;
}