#include <fstream>
#include <algorithm>
#define NMAX 5005
#define GMAX 10005
using namespace std;

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

int V[GMAX];

int main()
{
    int G, N;
    fin >> N >> G;
    int w[NMAX], p[NMAX];
    for (int i = 1; i <= N; i++)
    {
        fin >> w[i] >> p[i];
    }

    for (int i = 1; i <= N; i++)
    {
        for (int j = G; j >= w[i]; j--)
        {
            V[j] = max(V[j], V[j - w[i]] + p[i]);
        }
    }

    fout << V[G] << endl;

    fin.close();
    fout.close();

    return 0;
}