#include <bits/stdc++.h>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
const int nmax = 5e3 + 10;
const int gmax = 1e4 + 5;

int n, g, w[nmax], dp[2][gmax], p[nmax];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    fin >> n >> g;
    for (int i = 1; i <= n; ++i) fin >> w[i] >> p[i];

    int l = 0;
    for (int i = 1; i <= n; ++i, l = 1 - l) {
        for (int G = 0; G <= g; ++G) {
            dp[1 - l][G] = dp[l][G];

            if (w[i] <= G) {
                dp[1 - l][G] = max(dp[1 - l][G], dp[l][G - w[i]] + p[i]);
            }
        }
    }

    fout << dp[l][g];
    return 0;
}