#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 5005, G_MAX = 10005;
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()
{
    dp[0] = 0;
    for(int i = 1; i <= G; i++)
        dp[i] = -1;

    int crMaxSum = 0;
    for(int i = 0, j; i < N; i++)
    {
        for(j = crMaxSum; j >= 0; j--)
            if(dp[j] != -1 && j + w[i] <= G)
                dp[j + w[i]] = max(dp[j+w[i]], dp[j] + p[i]);

        crMaxSum = min(crMaxSum + w[i], G);
    }

    for(int i = G; i >= 0; i++)
        if(dp[i] != -1)
        {
            cout << dp[i] << '\n';
            break;
        }
}

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

    ReadInput();
    Solve();

    return 0;
}