#include <bits/stdc++.h>

using namespace std;

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

int n, G, w, p, d[2][10005];
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[1][j] = max(d[0][j], j - weight[i] >= 0 ? d[0][j - weight[i]] + profit[i] : 0);
        swap(d[0], d[1]);
    }
        
    g << d[0][G];

    return 0;
}