#include <bits/stdc++.h>

using namespace std;

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

int n, G, w, p, d[5000][10000];
vector<int> weight, profit;

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

    weight.push_back(0);
    profit.push_back(0);

    while (n--)
        f >> w >> p,
        weight.push_back(w),
        profit.push_back(p);

    for (int i = 1; i < weight.size(); ++i)
        for (int j = 1; j <= G; ++j)
            d[i][j] = max(d[i - 1][j], j - weight[i] >= 0 ? d[i - 1][j - weight[i]] + profit[i] : 0);

    g << d[weight.size() - 1][G];

    return 0;
}