#include<stdio.h>
long x[5002],i,j,n,m,k,l,a,z,s[5002],y[5002];
int main()
{
	freopen("pali.in","r",stdin);
	freopen("pali.out","w",stdout);

	scanf("%ld%ld",&n,&m);
	for (i=1;i<=n;i++)
	scanf("%ld%ld",&x[i],&y[i]);
	s[0]=1;
	for (i=1;i<=n;i++)
		for (j=m;j>=0;j--)
			if (s[j]&&s[j+x[i]]<s[j]+y[i]) {s[j+x[i]]=s[j]+y[i];}
	z=2000000000;
	for (i=m;i<=5001;i++)
	if (s[m]<z) {k=i;z=s[m];}
	printf("%ld\n",z-1);
	return 0;
}