#include <bits/stdc++.h>

using namespace std;

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

#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second

const int NMAX = 5e3 + 30;
const int INF = 0x3f3f3f3f;

int n, t, v[NMAX], gr[NMAX * 2], gmax, dp[2][NMAX*2];

void read()
{
    in >> n >> gmax;
    for (int i = 1; i <= n; i++)
        in >> gr[i] >> v[i];
}

void solve()
{
    for (int i=1; i<=n; i++, t ^= 1)
        for (int g=0; g<=gmax; g++)
        {
            dp[t][g] = dp[!t][g];
            if (g >= gr[i]) 
                dp[t][g] = max(dp[t][g], dp[!t][g - gr[i]] + v[i]);

        }
    
    out<<dp[!t][gmax];
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);

    read();
    solve();

    return 0;
}