#include <fstream>

using namespace std;

ifstream cin ("rucsac.in");
ofstream cout ("rucsac.out");

const int MAX_N = 5001;
const int MAX_G = 10000;

struct t_object {
    int greutate;
    int profit;
};
int memo[MAX_N][MAX_G];

int dp_profit (int idx, int capacitate, t_object objs[]){
    if (idx == 0)
        return 0;
    if (capacitate == 0)
        return 0;
    if (memo[idx][capacitate] != 0)
        return memo[idx][capacitate];
    if (objs[idx].greutate > capacitate){
        memo[idx][capacitate] = dp_profit (idx - 1, capacitate, objs);
        return memo[idx][capacitate];
    }

    int profit1 = dp_profit(idx-1, capacitate, objs);
    int new_capacitate = capacitate - objs[idx].greutate;
    int profit2 = objs[idx].profit + dp_profit(idx-1, new_capacitate, objs);
    memo[idx][capacitate] = max(profit1, profit2);
    return memo[idx][capacitate];
}
int main()

{
    int nr_elem, max_gr;
    t_object objs[MAX_N];

    cin >> nr_elem >> max_gr;

    for (int i = 1; i <= nr_elem; i++){
        int greutate, profit;
        cin >> greutate >> profit;
        t_object obj = {greutate, profit};
        objs[i] = obj;
    }

    cout << dp_profit(nr_elem, max_gr, objs);
    return 0;
}