#include<stdio.h>
	FILE *f , *g ;
	int n , w[5001] , p[5001] , s  , i  , x;
	long sol[2][10001];
	
	void citire();
	void solve();
	void tipar();
	long max(long x , long y)
	{
		if(x > y)
			return x;
		return y;
	}
	
	int main()
	{
		citire();
		solve();
		tipar();
		return 0;
	}
	
	void citire()
	{
		f=fopen("rucsac.in" , "r");
		fscanf(f , "%d%ld" , &n , &s );
		for(int i = 1 ; i<= n ; ++i )
			fscanf(f , "%d%d" , &w[i] , &p[i] );
		fclose(f);
	}
	
	void solve()
	{
		for(i = 1 , x = 0 ; i<= n ; ++i , x = 1-x )
			for(int j = 1 ; j <= s ; ++j )
			{
				if(w[i] > j)
					sol[x][j] = sol[1-x][j];
				if(w[i] <= j )
					sol[x][j] = max(sol[1-x][j] , p[i]+sol[1-x][j-w[i]]);
			}
	}
	
	void tipar()
	{
		g=fopen("rucsac.out" , "w" );
		fprintf(g , "%ld" , sol[1-x][s]);
		fclose(g);
	}