{\rtf1\ansi\ansicpg1252\cocoartf949\cocoasubrtf430
{\fonttbl\f0\fnil\fcharset0 LucidaGrande;}
{\colortbl;\red255\green255\blue255;}
\margl1440\margr1440\vieww13380\viewh12700\viewkind0
\deftab720
\pard\pardeftab720\ql\qnatural

\f0\fs22 \cf0 #include<stdio.h>\
#include<string.h>\
#define G 1002\
#define W 5002\
\
long sol[2][W],eg[G],cg[G],n,k,i,j,w;\
\
long min(long a,long b)\
\{\
	if (a<b) return a;\
	else	 return b;\
\}\
\
int main()\
\{\
	freopen("energii.in","r",stdin);\
	freopen("energii.out","w",stdout);\
\
	scanf("%ld %ld",&n,&k);\
	for(i=1;i<=n;i++)\
		scanf("%ld %ld",&eg[i],&cg[i]);\
\
	for (j=1;j<=k;j++)\
		if (eg[1]>=j)\
			sol[0][j]=cg[1];\
		else\
			sol[0][j]=2000000000;\
			\
	for(i=2;i<=n;i++)\
	\{\
		for(j=1;j<=k;j++)\
		\{\
			if (eg[i]>=j)	\
				sol[(i+1)%2][j]=cg[i];\
			else \
				sol[(i+1) % 2][j]=2000000000;\
\
			if (j-eg[i]>0)\
				sol[(i+1)%2][j]=min(sol[i % 2][j-eg[i]]+cg[i],sol[i % 2][j]);\
			else\
                        		sol[(i+1)%2][j]=min(sol[(i+1)%2][j],sol[i % 2][j]);\
\
		\}\
	\}\
\
	if (sol[(n+1) % 2][k]==2000000000)\
		printf("%ld\\n",-1);\
	else\
		printf("%ld\\n",sol[(n+1) %2][k]);\
	return 0;\
\}\
}