#include <iostream>
#include <fstream>
using namespace std;

//Variabile var 1
int W[5001], P[5001];
int Optim[10001];

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];
    }

    Optim[0] = 0;
    int sol = 0;

    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 (Optim[j + W[i]] > sol)
                    sol = Optim[j + W[i]];
            }
        }
    out << sol;
    return 0;
}