#include <iostream>
#include <fstream>

using namespace std;

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

int n, g, G[5001], P[5001], Dp[10001];

int main()
{
    fin >> n >> g;
    for (int i = 1; i <= n; ++i)
        fin >> G[i] >> P[i];
    for (int i = 1; i <= n; ++i)
    {
        for (int j = g - G[i]; j >= 0; --j)
            Dp[j + G[i]] = max(Dp[j + G[i]], Dp[j] + P[i]);
    }
    fout << Dp[g];

    return 0;
}