#include <stdio.h>
#include <algorithm>

FILE *in = fopen("rucsac.in", "r");
FILE *out = fopen("rucsac.out", "w");

int N, W;
int t[5005][2];

long C[2][10005];

void _read()
{
	fscanf(in, "%d %d", &N, &W);
	for(int i=1; i<=N; ++i)
	{
		fscanf(in, "%d %d", &t[i][0], &t[i][1]);
	}
}

int main()
{
	_read();

	for(int j=0; j<=W; ++j)
	{
		C[0][j] = 0;
	}

	for(int i=1; i<=N; ++i)
	{
		C[1][0] = 0;

		for(int j=1; j<=W; ++j)
		{
			
			if(j < t[i][0])
				C[1][j] = C[0][j];
			else
				C[1][j] = std::max(C[0][j], t[i][1] + C[0][j - t[i][0]]);
			
		}

		for(int j=1; j<=W; ++j)
		{
			C[0][j] = C[1][j];
		}
		
	}

	fprintf(out, "%ld", C[0][W]);

}