#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 5005, G_MAX = 10010;
int N, G;
int w[N_MAX], p[N_MAX];
int dp[G_MAX];

void SetInput(string name)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    (void)!freopen((name + ".in").c_str(), "r", stdin);
    (void)!freopen((name + ".out").c_str(), "w", stdout);
}

void ReadInput()
{
    cin >> N >> G;
    for (int i = 0; i < N; i++)
        cin >> w[i] >> p[i];
}

void Solve()
{
    // Initialize dp array
    for (int i = 0; i <= G; i++)
        dp[i] = -1;
    dp[0] = 0;  // Base case: sum 0 is always reachable with profit 0

    for (int i = 0; i < N; i++)
        for (int j = G; j >= w[i]; j--)
            if (dp[j - w[i]] != -1) // Only update if the previous sum is reachable
                dp[j] = max(dp[j], dp[j - w[i]] + p[i]);

    // Find the maximum profit
    int maxProfit = 0;
    for (int i = 0; i <= G; i++)
        if (dp[i] != -1)
            maxProfit = max(maxProfit, dp[i]);

    cout << maxProfit << '\n';
}

int main()
{
    SetInput("rucsac");

    ReadInput();
    Solve();

    return 0;
}