#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 5e3 + 2, Gmax = 1e4 + 2;

int n, G, dp[2][Gmax], niv, W;

struct backp
{
    int w, p;
}v[nmax];

int main()
{
    fin >> n >> G;

    for (int i=1; i<=n; ++i) fin >> v[i].w >> v[i].p;

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

            if (v[i].w <= j) dp[1-niv][j] = max(dp[1-niv][j], dp[niv][j-v[i].w] + v[i].p);
        }

    fout << dp[niv][G];
    return 0;
}