#define _CRT_SECURE_NO_WARNINGS
//#include<_dbdao.h>
#include<stdio.h>
#include<stdlib.h>
FILE *fin=fopen("rucsac.in","r"), *fout=fopen("rucsac.out","w");
int n,W,w[5001],val[5001],t[1000][1000];

void read()
{
	fscanf(fin,"%d %d",&n,&W);
	for(int i=1;i<=n;i++)
		fscanf(fin,"%d %d",&w[i],&val[i]);

}

int max(int a, int b)
{
	if(a>=b)
		return a;
	else
		return b;
}

void solve_knapsack()
{
	int i,j;

	for(i=1;i<=n;i++)
		for(j=0;j<=W;j++)
		{
			if(j>=w[i])
				t[i][j]= max(t[i-1][j], t[i-1][j-w[i]] + val[i]);
			else
				t[i][j]=t[i-1][j];
		}
	/*
	for(i=1;i<=n;i++)
	{
		for(j=0;j<=W;j++)
			fprintf(fout,"%d ",t[i][j]);
		fprintf(fout,"\n");
	}*/
fprintf(fout,"%d",t[n][W]);
}

int main()
{
	read();
	solve_knapsack();
	fcloseall();
	return 0;
}