#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define FARA_NUMAR 1005
#define bamveu_cu_nikeleu void
#define CEA_MAI_TARE_COMBINATIE 5894759
#define LANTZ_DA_HAUR_MERITA_SHMEKERU 0
FILE *teancu_da_lei_vechi=fopen("energii.in", "r"), *teancu_da_euroi=fopen("energii.out", "w");
long interlop_adevarat[10011000], bashtan, trimit_puradelu_n_spania, chermeza, shuteste_fratelele_de_la_francia, jupan;

typedef struct am_valoare_si_bishtari
{
	int am_putere_si_valoare, bishnitzarii_dau_cu_banii;
};

am_valoare_si_bishtari dau_cu_zaru_6_6[FARA_NUMAR];

bamveu_cu_nikeleu da_valoare_la_jupan()
{
	long c=0;
	fscanf(teancu_da_lei_vechi, "%ld%ld", &chermeza, &shuteste_fratelele_de_la_francia);
	for (bashtan=1;bashtan<=chermeza;bashtan++)
	{
		fscanf(teancu_da_lei_vechi, "%d%d", &dau_cu_zaru_6_6[bashtan].am_putere_si_valoare, &dau_cu_zaru_6_6[bashtan].bishnitzarii_dau_cu_banii);
		jupan+=dau_cu_zaru_6_6[bashtan].am_putere_si_valoare;
		c+=dau_cu_zaru_6_6[bashtan].bishnitzarii_dau_cu_banii;
	}
	if (jupan<shuteste_fratelele_de_la_francia)
	{
		fprintf(teancu_da_euroi, "-1");
		exit(LANTZ_DA_HAUR_MERITA_SHMEKERU);
		fclose(teancu_da_lei_vechi);
		fclose(teancu_da_euroi);
	}
	else
		if (jupan==shuteste_fratelele_de_la_francia)
		{
			fprintf(teancu_da_euroi, "%ld", c);
			exit(LANTZ_DA_HAUR_MERITA_SHMEKERU);
			fclose(teancu_da_lei_vechi);
			fclose(teancu_da_euroi);
		}
	memset(interlop_adevarat, CEA_MAI_TARE_COMBINATIE, 10010500);
}

bamveu_cu_nikeleu dau_bishtari_la_lautari()
{
	for (bashtan=1;bashtan<=chermeza;bashtan++)
	{
		for (trimit_puradelu_n_spania=shuteste_fratelele_de_la_francia;trimit_puradelu_n_spania>=0;trimit_puradelu_n_spania--)
			if (interlop_adevarat[trimit_puradelu_n_spania]!=CEA_MAI_TARE_COMBINATIE&&interlop_adevarat[trimit_puradelu_n_spania+dau_cu_zaru_6_6[bashtan].am_putere_si_valoare]>interlop_adevarat[trimit_puradelu_n_spania]+dau_cu_zaru_6_6[bashtan].bishnitzarii_dau_cu_banii)
				interlop_adevarat[trimit_puradelu_n_spania+dau_cu_zaru_6_6[bashtan].am_putere_si_valoare]=interlop_adevarat[trimit_puradelu_n_spania]+dau_cu_zaru_6_6[bashtan].bishnitzarii_dau_cu_banii;
			if (interlop_adevarat[dau_cu_zaru_6_6[bashtan].am_putere_si_valoare]>dau_cu_zaru_6_6[bashtan].bishnitzarii_dau_cu_banii)
				interlop_adevarat[dau_cu_zaru_6_6[bashtan].am_putere_si_valoare]=dau_cu_zaru_6_6[bashtan].bishnitzarii_dau_cu_banii;
	}
}

bamveu_cu_nikeleu mor_dusmanii_cand_scot_banu()
{
	long cel_mai_shukar_puradel=CEA_MAI_TARE_COMBINATIE;
	for (bashtan=shuteste_fratelele_de_la_francia;bashtan<=jupan;bashtan++)
		if (interlop_adevarat[bashtan]<cel_mai_shukar_puradel)
			cel_mai_shukar_puradel=interlop_adevarat[bashtan];
	fprintf(teancu_da_euroi, "%ld", cel_mai_shukar_puradel);
}

int main()
{
	da_valoare_la_jupan();
	dau_bishtari_la_lautari();
	mor_dusmanii_cand_scot_banu();
	fclose(teancu_da_lei_vechi);
	fclose(teancu_da_euroi);
	return (LANTZ_DA_HAUR_MERITA_SHMEKERU);
}