#include <iostream>
#include <fstream>
#define NMAX 5000
#define GMAX 10000

using namespace std;

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

int N, G;
int knapsack[2][GMAX + 1];
int weights[NMAX], prices[NMAX];

int main()
{
    fin >> N >> G;
    for (int i = 0; i < N; ++i) fin >> weights[i] >> prices[i];

    for (int i = 1; i <= N; ++i) {
        for (int g = 0; g <= G; ++g)
            knapsack[1][g] = max(knapsack[0][g], (weights[i - 1] <= g ? knapsack[0][g - weights[i - 1]] + prices[i - 1] : 0));
        for (int g = 0; g <= G; ++g)
                knapsack[0][g] = knapsack[1][g];
    }

    fout << knapsack[0][G];

    fin.close();
    fout.close();
    return 0;
}