#include<cstdio>

int n,w,i,j,s,max,maxx;

int a[1000],b[1000];

int f[5000];



int main()
{
	
	freopen("energii.in","r",stdin);
	freopen("energii.out","w",stdout);
	
	scanf("%d%d" , &n , &w);
	
	for (i=1;i<=n;i++)
	{
		scanf("%d%d" , &a[i], &b[i]);
		if (a[i]>max) max=a[i];
	}
	
	
	for (i=1;i<=n;i++)
	{
		for ( j=w-1;j>=1;j--)
			if (f[j])
				if ( f[j]+b[j] > f[j+a[i]])
				f[j+a[i]]=f[j]+b[j];
		
		if (!f[a[i]]) f[a[i]]=b[i];
	}
	
	for (j=s;j<=s+max;j++)
		if (f[j]<maxx || maxx==0) maxx=f[j];
	
	printf("%d", maxx);
	
	return 0;
}