#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

#define MAXN 5001
#define MAXG 10001

int DP[2][MAXG];
int P[MAXN], W[MAXN];
int N, G;

int main()
{
    fin >>N >>G;
    for (int i = 1; i <= N; ++i)
		fin >>W[i] >>P[i];
	int line = 0;
    for (int i = 1; i <= N; ++i, line = 1 - line)
		for (int curr_weight = 0; curr_weight <= G; ++curr_weight)
		{
			DP[1-line][curr_weight] = DP[line][curr_weight];

			if (W[i] <= curr_weight)
				DP[1-line][curr_weight] = max (DP[1-line][curr_weight], DP[line][curr_weight - W[i]] + P[i]);
		}

	fout <<DP[1][G];

    return 0;
}