#include <fstream>
#define maxim(a,b) (a>b?a:b)
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,G,m=0,pm;

struct obiecte{
	int w;
	int p;
};
obiecte a[5001];
int val[10001];

int main(void){
	register int i,j;
	
	f>>n>>G;
	for(i=1;i<=n;i++)
		f>>a[i].w>>a[i].p;
	
	for(i=1;i<=n;i++){
		for(j=G;j>=1;j--){
			if(val[j]>0 && j+a[i].w<=G){
				val[j+a[i].w]=maxim(a[i].p+val[j],val[j+a[i].w]);
				if(m<a[i].p+val[j])
					m=a[i].p+val[j];
			}
		}
		//pt 0
		val[a[i].w]=maxim(a[i].p,val[a[i].w]);
		if(val[a[i].w]>m)
			m=val[a[i].w];
	}
	g<<m;
	return 0;
}