#include <fstream>
#include <iostream>
#include <algorithm>

#define MAX_N 5001
#define MAX_G 10001

std::ifstream in("rucsac.in");
std::ofstream out("rucsac.out");

int dp[2][MAX_G];
int W[MAX_N], P[MAX_N];
int N, G;

void read_input_data()
{
    in >> N >> G;
    for (int i = 1; i <= N; i++) {
        in >> W[i] >> P[i];
    }
}

int apply_knapsack_dp_algorithm()
{
    int L = 1;
    for (int i = 1; i <= N; i++, L = 1 - L) {
        for (int j = 1; j <= G; j++) {
            dp[L][j] = dp[1 - L][j];
            if (W[i] <= j) {
                dp[L][j] = std::max(dp[L][j], dp[1 - L][j - W[i]] + P[i]);
            }
        }
    }

    return dp[1 - L][G];
}

int main()
{
    read_input_data();
    int max_profit = apply_knapsack_dp_algorithm();

    out << max_profit;

    return 0;
}