#include <bits/stdc++.h>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n, G, sol;
int g[5005], v[5005];
int dp[2][5005];
int main()
{
    int i, j, ind;
    fin >> n >> G;
    for (i = 1; i <= n; i++)
        fin >> g[i] >> v[i];

    ind = 1;
    for (i = 1; i <= n; i++, ind ^= 1)
    {
        for (j = G; j >= 0; j--)
            if (j >= g[i])
                dp[ind][j] = max(dp[ind ^ 1][j], dp[ind ^ 1][j - g[i]] + v[i]);
            else
                dp[ind][j] = dp[ind ^ 1][j];
    }
    ind ^= 1;
    fout << dp[ind][G] << "\n";

    return 0;
}