/// knapsack problem
#include <fstream>
#define NMax 5010
#define GMax 10010
///#define f cin
///#define g cout
using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int n, G, w[NMax], p[NMax];
int ant[NMax], sol;

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

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

    g << sol << '\n';

    return 0;
}