#include<stdio.h>
int d[5][5000010],g[1010],w[1010];
inline int max (int a, int b)
{
	if(a>b) return a;
	return b;
}

int main()
{
	freopen("energii.in","r",stdin);
	freopen("energii.out","w",stdout);
	int i,n,j,G,la,lc,sum,min;
	scanf("%d%d",&n,&G);
	sum=0;
	for(i=1;i<=n;i++)
		{
			scanf("%d%d",&g[i],&w[i]);
			sum+=w[i];
		}
	for(i=1;i<=n;i++)
		for(j=1;j<=sum;j++)
			{
				la=(i+1)%2;
				lc=i%2;
				if(g[i]>j)
					d[lc][j]=d[la][j];
				if(g[i]<=j)
					d[lc][j]=max(d[la][j],d[la][j-g[i]]+w[i]);
			}
	min=5000100;
	for(j=G;j<=sum;j++)
		if(d[lc][j]<min)
			min=d[lc][j];
	printf("%d\n",d[lc][G]);
	return 0;
}