#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define INF 2000000000
#define MaxN 10005
using namespace std;
    
FILE *IN,*OUT;
int N,G,val,w,v[MaxN],Max;
int main()
{
	IN=fopen("rucsac.in","r");
	OUT=fopen("rucsac.out","w");
	
	fscanf(IN,"%d%d",&N,&G);
	v[0]=1;
	for(int i=1;i<=N;i++)
	{
		fscanf(IN,"%d%d",&w,&val);
		for(int j=G-w;j>=0;j--)
			if(v[j])
				v[j+w]=max(v[j+w],v[j]+val),Max=max(v[j+w],Max);
	}
	fprintf(OUT,"%d",Max-1);
	return 0;
}