#include <stdio.h>
#include <limits.h>

#define WMAX 15001

int main()
{
	FILE *fi, *fo;

	int G, W, Wmax=1;
	int GC[1010], GE[1010], T[WMAX], TT[WMAX];

	int i, j, found=1, Cmin;

	fi=fopen("energii.in", "r");
	fo=fopen("energii.out", "w");

	
	fscanf(fi, "%d %d", &G, &W);

	for(i=0; i<G; i++)
	{
		fscanf(fi, "%d %d", &GE[i], &GC[i]);
	}	

	Wmax=0;

	for(i=0; i<G; i++)
	{
		if (Wmax + GE[i] < WMAX)
			Wmax+=GE[i];

		for(j=0; j<WMAX; j++)
		{
			TT[j]=0;
		}

		for(j=0; j<=Wmax; j++)
		{
			if(j==0)
			{
				TT[GE[i]]=GC[i];
			} else {
				if(T[j] && j + GE[i] < WMAX){
					TT[j+GE[i]]=T[j]+GC[i];
				}
			}
		}
		for(j=0; j<WMAX; j++)
		{
			if((TT[j]<T[j]&&TT[j])||((!T[j])&&TT[j])){
				T[j]=TT[j];
			}
		}

	}	

	/*for(i=W, j=W; i>0, j<=Wmax; i--, j++)
	{
	
	}*/

	Cmin = INT_MAX;
	for(i=W; i<=Wmax; i++)
	{
		if(T[i]<Cmin&&T[i]>0)
		{
			Cmin=T[i];
		}	
	}
	
	fprintf(fo, "%d", Cmin);

	return 0;
}