#include<stdio.h>
#define G 1002
#define W 5002

int sol[G][W],eg[G],cg[G],n,k,i,j,w;

int min(int a,int b)
{
	if (a<b) return a;
	else	 return b;
}

int main()
{
	freopen("energii.in","r",stdin);
	freopen("energii.out","w",stdout);
	scanf("%d %d",&n,&k);
	for(i=1;i<=n;i++)
		scanf("%d %d",&eg[i],&cg[i]);
	for (j=1;j<=k;j++)
		if (eg[1]>=j)
			sol[1][j]=cg[1];
		else
                	sol[1][j]=30000;
	for(i=2;i<=n;i++)
		for(j=1;j<=k;j++)
		{
			if (eg[i]>=j)	sol[i][j]=cg[i];
			else
                			sol[i][j]=30000;
			for (w=j-eg[i];w<j && w>0;w++)
				sol[i][j]=min(sol[i][j],sol[i-1][w]+cg[i]);
			for (w=1;w<=i-1;w++)
				sol[i][j]=min(sol[w][j],sol[i][j]);
		}
	printf("%d\n",sol[n][k]);
	return 0;
}