#include <fstream>
#include <iostream>

using namespace std;

ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");

int optim[10005], w[5005], p[5005];

int main()
{
    int n, G, sol = 0;

    fin >> n >> G;

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

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

    fout << sol;

    return 0;
}