#include<cstdio>
#define max(a,b) a>b?a:b
void read(),solve();
int i,j,G,W,EG[1001],CG[1001],M[1001][1001],SC,SE;
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("energii.in","r",stdin);
	freopen("energii.out","w",stdout);
	scanf("%d%d",&G,&W);
	for(i=1;i<=G;i++)
	{
		scanf("%d%d",&EG[i],&CG[i]);
		SC+=CG[i];SE+=EG[i];
	}
}
void solve()
{
	for(i=1;i<=G;i++)
		for(j=1;j<=SE-W;j++)
		{
			if(EG[i]>j){M[i][j]=M[i-1][j];continue;}
			M[i][j]=max(M[i-1][j],M[i-1][j-EG[i]]+CG[i]);
		}
	printf("%d\n",SC-M[G][SE-W]);
}