#include    <fstream>

using namespace std;

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

#define ARRAY_MAX 10000

int Weight[ARRAY_MAX], Cost[ARRAY_MAX], Best[ARRAY_MAX];
int N, G, result;

void Read() {
    fin >> N >> G;

    for (int i = 1; i <= N; i++)
        fin >> Weight[i] >> Cost[i];
}

int KnapSack() {
    for (int i  = 1; i <= N; i++)
        for (int j = G - Weight[i]; j >= 0; j--)
            if (Best[j + Weight[i]] < Best[j] + Cost[i]) {
                Best[j + Weight[i]] = Best[j] + Cost[i];

                if (Best[j + Weight[i]] > result)
                    result = Best[j + Weight[i]];
            }

    return result;
}

int main() {
    Read();
    fout << KnapSack();
}