#include <stdio.h>
#define lung 5000000
#define lng 1000

int m[lung+1],G,E,Sum;
struct generator
{int e,c;} a[lng];

void citire()
{
	int i;
	freopen("energii.in","r",stdin);
	scanf("%d%d",&G,&E);
	for (i=0;i<G;i++)
		scanf("%d%d",&a[i].e,&a[i].c),
		Sum+=a[i].e;
	fclose(stdin);
}

int rez()
{
	int i,j,k;
	m[0]=1;
	for (i=0;i<G;i++)
	{
		for (j=Sum-a[i].e;j>=0;j--)
			if (m[j] && (!m[ j + a[i].e ] || m[ j + a[i].e ] > m[j]+ a[i].c))
				m[j + a[i].e ] = m[j] + a[i].c;
	}
	for (k=Sum;!m[k];k--);
	for (i=k-1;i>=E;i--)
		if ( m[k]>m[i] && m[i] )
			k=i;
	return m[k]-1;
}

void scriere()
{
	freopen("energii.out","w",stdout);
	printf("%d\n",rez());
	fclose(stdout);
}

int main()
{
	citire();
	scriere();
	return 0;
}