#include<stdio.h>
#define maxn 5001
#define maxg 10001
using namespace std;
int W[maxn],P[maxn],N,G,i,j,sol;
int O[maxg];
int main() 
{
	freopen("rucsac.in", "r", stdin);
	freopen("rucsac.out", "w", stdout);
	scanf("%d%d",&N,&G);
	for (i=1;i<=N;++i) 
		scanf("%d%d",&W[i],&P[i]);
	for(i=1;i<=N;++i)
		for(j=G-W[i];j>=0;--j)
			if(O[j+W[i]]<O[j]+P[i])
			{
				O[j+W[i]]=O[j]+P[i];
				if(O[j+W[i]]>sol)
					sol=O[j+W[i]];
			}
	printf("%d", sol);
	return 0;
}