#include <fstream>
#include <algorithm>

using namespace std;

int n, g, w[5005], p[5005], d[5005][10005];

int main()
{
    ifstream f("rucsac.in");
    ofstream out("rucsac.out");

    f >> n >> g;

    for(int i = 1; i <= n; ++i)
        f >> w[i] >> p[i];


    for(int i = 1; i <= n; ++i)
        for(int cw = 0; cw <= g; ++cw)
    {
        d[i][cw] = d[i-1][cw];

        if(w[i] <= cw)
            d[i][cw] = max(d[i][cw], d[i-1][cw-w[i]] + p[i]);
    }

    out << d[n][g];
    return 0;
}