#include <iostream>
#include <fstream>
#define maxN 5002
#define maxG 10002

using namespace std;

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

int n, G, Op[maxG], W[maxN], P[maxN], sol;

int main () {
    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 (Op[j+W[i]] < Op[j] + P[i]) {
                Op[j+W[i]] = Op[j] + P[i];
                if (Op[j+W[i]] > sol)
                    sol = Op[j+W[i]];
            }
        }
    }
    fout << sol;
}