#include <stdio.h>
#include <string.h>
#define MARE 5898487
FILE *f=fopen("energii.in", "r"), *g=fopen("energii.out", "w");
long sum[1001100], e[1005], c[1005], i, gen, need, j, s;

void citeste(void)
{
	fscanf(f, "%ld%ld", &gen, &need);
	for (i=1;i<=gen;i++)
		fscanf(f, "%ld%ld", &e[i], &c[i]);
	fclose(f);
}

void sume(void)
{
	for (i=1;i<=gen;i++)
		s+=e[i];
	for (i=1;i<=s;i++)
		sum[i]=MARE;
	for (i=1;i<=gen;i++)
	{
		for (j=s;j>0;j--)
			if (sum[j]!=MARE&&c[i]+sum[j]<sum[e[i]+j])
				sum[e[i]+j]=sum[j]+c[i];
		if (sum[e[i]]>c[i])
			sum[e[i]]=c[i];
	}
}

void gaseste(void)
{
	long min=MARE;
	for (i=need;i<=s;i++)
		if (sum[i]<min)
			min=sum[i];
	fprintf(g, "%ld", min);
	fclose(g);
}		
		
int main(void)
{
	citeste();
	sume();
	gaseste();
}