#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int dp[2][10001];
int g[5001], c[5001];
int main()
{
    int N, G, i, j, l;
    fin >> N >> G;
    for (i = 1; i<=N; i++)
        fin >> g[i] >> c[i];
    for (i = 1, l = 0; i<=N; i++, l = 1-l)
        for (j = 1; j<=G; j++)
        {
            dp[l][j] = dp[1-l][j];
            if (g[i] <= j)
                dp[l][j] = max(dp[l][j], dp[1-l][j-g[i]] + c[i]);
        }
    fout << dp[1-l][G];
    return 0;
}