#include <stdio.h>
#include <stdlib.h>


short int *vector, *cost, *energie;	//vector se foloseste pentru generarea de solutii
short int G;	//numarul de generatoare
short int W;	//cantitatea de energie necesara repornirii centralei
int cost_minim=11000000,cost_curent=0,putere_curenta=0;

inline void init(short k)
	{
	if (k == 0) *(vector+k)=-1;
		else
			*(vector+k)=*(vector+k-1);
	}

inline int exista(short k)
	{
	return (*(vector+k) < G-1);
	}

inline int cont()
	{
	return (cost_curent < cost_minim);
	};

inline int solutie()
	{
	return (putere_curenta >= W);
	}
   
 /*
void tipar(short int k)
	{
	for (int i=0;i<=k;i++)
		printf("%d ",*(vector+i));
   printf("%d %d",cost_curent,putere_curenta);
	printf("\n");
	}
*/

void bkt(short int k)
	{
	init(0);
	while (k>-1) 
		{
		if (exista(k))
			{
			(*(vector+k))++;
         if (k == 0)
			{
			cost_curent=*(cost+(*vector));
			putere_curenta=*(energie+(*vector));
			}
         else {
			cost_curent=cost_curent-cost[*(vector+k)-1]+cost[*(vector+k)];
			putere_curenta=putere_curenta-energie[*(vector+k)-1]+energie[*(vector+k)];
         		}
			if (cont()) 
				{
				if (solutie())
            	{
   				cost_minim=cost_curent;
               }
				  	else
					 	{
						k++;
						init(k);
						cost_curent=cost_curent+cost[*(vector+k)];
						putere_curenta=putere_curenta+energie[*(vector+k)];
						}
				} 
			
			}
		else
      		{
            k--;
            cost_curent-=cost[*(vector+k+1)];
            putere_curenta-=energie[*(vector+k+1)];
            }
			 
		}
	}

int main()
{
FILE *in;
in=fopen("energii.in","r");
fscanf(in,"%hd",&G);
fscanf(in,"%hd",&W);
int i=0;

//alocarea memoriei pentru cei trei vectori de cost, valoare si solutie a procedurii de backtracking
cost=new short[G];
energie=new short[G];
vector=new short[G];

//printf("%d %d",G,W);
for (;i<G;i++)
	{
	fscanf(in,"%hd %hd",energie+i,cost+i);
	}

bkt(0);

fclose(in);
in=fopen("energii.out","w");
if (cost_minim == 11000000) fprintf(in,"%d",-1);
	else fprintf(in,"%d",cost_minim);

//inchiderea fisierelor si incheierea executiei
fclose(in);
return 0;
}