#include <fstream>

using namespace std;

const int MAXG = 10002;
const int MAXN = 5003;

int smax[MAXG];
int w[MAXN], p[MAXN];

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

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

    for (int j = 1; j <= n; j++)
    {
        for (int i = g - w[j]; i >= 0; i--)
        {
            if (smax[w[j]+i] < smax[i] + p[j])
                smax[w[j]+i] = smax[i] + p[j];
        }
    }

    out << smax[g] << '\n';

    return 0;
}