#include <iostream>
#include <fstream>

using namespace std;

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

int n, g, w[5010], p[10010], v[10010], i, j, maxi = 0;

int main()
{
    f >> n >> g;
    for (i = 1; i <= n; i ++)
        f >> w[i] >> p[i];
    for (i = 1; i <= n; i ++)
        for (j = g; j >= 1; j --)
    {
        if (v[j + w[i]] < v[j] + p[i])
        {
            v[j + w[i]] = v[j] + p[i];
            if (v[j + w[i]] > maxi)
                maxi = v[j + w[i]];
        }
    }
    go << maxi;
}