#include<string.h>

#include<stdio.h>

#include<vector>

#include<algorithm>

#define maxn 5001

#define maxg 10001



using namespace std;



int W[maxn], P[maxn];

int Optim[maxg];



int main() {



	freopen("rucsac.in", "r", stdin);

	freopen("rucsac.out", "w", stdout);

	int N, G;

	scanf("%d %d", &N, &G);



	for (int i = 1; i <= N; ++i) {

		scanf("%d %d", &W[i], &P[i]);

	}



	Optim[0] = 0;

	int sol = 0;



	for( int i = 1; i <= N; ++i)

		for( int j = G - W[i]; j >= 0; --j) {

			if( Optim[j+W[i]] < Optim[j] + P[i] )

			{

				Optim[j+W[i]] = Optim[j] + P[i];

				if( Optim[j+W[i]] > sol)

					sol = Optim[j+W[i]];

			}

		}

	printf("%d", sol);

	return 0;

}