#include <iostream>
#include<fstream>

using namespace std;

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

#define MAXN 5010
#define MAXG 10010

int DP[2][MAXG],N, G, Pmax, W[MAXN], P[MAXN];

int main()
{
    int i, cw;

    fin>>N>>G;

    for (i=1; i<=N; i++)
        fin>>W[i]>>P[i];

    for (i=1; i<=N; i++)
        for (cw=1; cw<=G; cw++)
            if (W[i]>cw)
                DP[i%2][cw] = DP[(i+1)%2][cw];
            else
                DP[i%2][cw] = max(DP[(i+1)%2][cw], DP[(i+1)%2][cw-W[i]] + P[i]);

    Pmax = DP[N%2][G];

    fout<<Pmax<<endl;

    return 0;
}