#include<fstream.h>

ifstream fin("energii.in");
ofstream fout("energii.out");

struct centrala {int e,c;} g[1002];

int n,w,C[1002][5002],s[1002]={0};

int main()
{
	fin>>n>>w;
	for(int i=1;i<=n;i++)
		fin>>g[i].e>>g[i].c;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=w;j++) 
			if((g[i].e<=j)&&(g[i].c+C[i-1][j-g[i].e]>C[i-1][j])) {
				C[i][j]=g[i].c+C[i-1][j-g[i].e];
				s[i]=1;
			}
			else
				C[i][j]=C[i-1][j];
		
	if(C[n][w]==w) fout<<C[n][w];
	else {
		int min=32000, imin;
		for(i=1;i<=n;i++)
			if(!s[i]&&g[i].c<min) {
				min=g[i].c;
				imin=i;
		}
		C[n][w]+=g[imin].c;
	}
	
	return 0;
}