#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);
}