#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[NMAX + 1][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[i][g] = max(knapsack[i - 1][g], (weights[i - 1] <= g ? knapsack[i - 1][g - weights[i - 1]] + prices[i - 1] : 0));

    fout << knapsack[N][G];
}