#include <bits/stdc++.h>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

typedef pair < int, int > PII;

const int NMAX = 5e3 + 5, GMAX = 1e4 + 5;

int N, G;
int dp[GMAX];

PII A[NMAX];

static inline void Read ()
{
    f.tie(NULL);

    f >> N >> G;

    for(int i = 1; i <= N; ++i)
        f >> A[i].first >> A[i].second;

    return;
}

static inline void Solve ()
{
    memset(dp, -1, sizeof(dp));

    int Sum = 0;

    dp[0] = 0;

    for(int i = 1; i <= N; ++i)
    {
        int W = A[i].first;
        int P = A[i].second;

        int Limit = min(max(0, G - W), Sum);

        for(int j = Limit; j >= 0; --j)
            if(dp[j] == -1)
                continue;
            else
                dp[j + W] = (dp[j + W] == -1) ? (dp[j] + P) : (max(dp[j + W], dp[j] + P));

        Sum += W;
    }

    return;
}

static inline void Write ()
{
    int ans = 0;

    for(int i = 0; i <= G; ++i)
        if(dp[i] != -1)
            ans = max(ans, dp[i]);

    g << ans << '\n';

    return;
}

int main()
{
    Read();

    Solve();

    Write();

    return 0;
}