#include <stdio.h>

#define IN_FILE "energii.in"
#define OUT_FILE "energii.out"

#define MAX_G 1000
#define MAX_W 5000
#define MAX_COST 10001000

int G, W;
int EG[MAX_G], CG[MAX_G];

void initialize_used(char use_vector[MAX_W][MAX_G], int max_energy, int max_generators)
{
	int i, j;
	for (i = 0; i <= max_energy; i++)
		for (j = 0; j < max_generators; j++)
			use_vector[i][j] = 0;
}

int not_already_used(int generator_index, char *use_vector)
{
	if (use_vector[generator_index] == 0)
		return 1;
	return 0;
}

void add_generator(char *target, char *source, int generator_index, int max_generators)
{
	int i;
	for (i = 0; i < max_generators; i++)
		target[i] = source[i];
	target[generator_index] = 1;
}

void one_generator(char *target, int generator_index, int max_generators)
{
	int i;
	for (i = 0; i < max_generators; i++)
		target[i] = 0;
	target[generator_index] = 1;
}

int main(void)
{
	int w, i;
	FILE *fin, *fout;
	int best_cost[MAX_W + 1];
	char used[MAX_W + 1][MAX_G];

	fin = fopen(IN_FILE, "r");
	fscanf(fin, "%d\n%d\n", &G, &W);
	for (i = 0; i < G; i++)
	{
		fscanf(fin, "%d %d", EG+i, CG+i);
	}
	fclose(fin);


	/* Initializarea costurilor minime */
	for (w = 1; w <= W; w++)
		best_cost[w] = MAX_COST;
	best_cost[0] = 0;

	/* SOLUTIA MEA NU TINE CONT DE FAPTUL CA NU POT SA REFOLOSESC UN GENERATOR DEJA FOLOSIT !!! 
	 * PENTRU ASTA AM NEVOIE DE SPATIU DE MEMORIE SUPLIMENTAR !
	 */
	/* Sunt (cel putin) doua feluri de a rezolva asta:
	 * Pastrez un vector suplimentar cu generatoarele pe care le-am folosit la fiecare minim pentru o anumita energie 
	 * Sau fac asa cum scrie wikipedia la knapsack problem
	 * (cele doua solutii practic fac in cele din urma acelasi lucru mi se pare mie! RAMANE DE VERIFICAT DACA E ASA !)
	 */
	initialize_used(used, W, G);

	/* Determinam rand pe rand costurile minime pentru toate cantitatile de energie de la 0 la W */
	for (w = 1; w <= W; w++)
	{
		//printf("Working out for energy %d\n", w);
		/* Incercand sa mai adaugam un generator la un cost deja generat */
		for (i = 0; i < G; i++)
			if (w > EG[i])
			{
				//printf("Generator %d produces less than energy %d\n", i, w);
				if ((best_cost[w] > (best_cost[w - EG[i]] + CG[i])) && (not_already_used(i, used[w - EG[i]])))
				{
					best_cost[w] = best_cost[w - EG[i]] + CG[i];
					add_generator(used[w], used[w - EG[i]], i, G);
					//printf("Adding generator %d for cost %d\n", i, best_cost[w]);
					//used[w] = used[w - EG[i]] + i;	//this syntax is clearly wrong for the compiler :) !!!
				}
			}
			else
			{
				//printf("Generator %d produces more than energy %d\n", i, w);
				/* Dar e posibil sa obtinem un cost mai bun folosind pur si simplu un generator care are mai multa putere decat avem nevoie ! */
				if (CG[i] < best_cost[w])
				{
					best_cost[w] = CG[i];
					one_generator(used[w], i, G);

					//printf("Adding *single* generator %d for cost %d\n", i, best_cost[w]);
					//used[w] = just i;
				}
			}
	}
/*
	printf("\n\n***\n\n");
	for(w = 0; w <= W; w++)
		printf("Cost for energy %d is %d\n", w, best_cost[w]);
*/
	if (best_cost[W] == MAX_COST)
		best_cost[W] = -1;

	fout = fopen(OUT_FILE, "w");
	fprintf(fout, "%d\n", best_cost[W]);
	fclose(fout);

	return 0;
}