#include <fstream>
#include <vector>

using namespace std;

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

int main()
{
    int n, G;
    in >> n >> G;

    vector<int> g(n + 1);
    vector<int> cost(n + 1);
    vector<int> dp(G + 1);

    for (int i = 1; i <= n; i++)
        in >> g[i] >> cost[i];

    for (int i = 1; i <= n; i++)
        for (int j = G; j >= g[i]; j--)
            dp[j] = max(dp[j], dp[j - g[i]] + cost[i]);

    out << dp[G];
    return 0;
}