// EmptyConsoleApp.cpp : Defines the entry point for the console application.
//

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

typedef struct nume{
    unsigned int cost, prod;
    //float value;
    struct nume *nextval, *prevval;
}energ;

int dinprog()
{
    FILE *in;
    unsigned int ngen = -1, enec = -1, i = 0, min = -1, used[1000], eavailable = 0, totalcost = 0, tempcost = 0, tempeavailable, first = 1, j;
    energ *e, *f, *mincost, *maxcost;
    
    in = fopen("energii.in", "r");

    if (in)
    {
        fscanf(in, "%u", &ngen);
    }
    else
    {
        return -1;
    }

    fscanf(in, "%u", &enec);

    i = 0;
    e = (energ*)calloc(ngen, sizeof(energ));
    f = e;

    while (i < ngen)
    {
        if (fscanf(in, "%u", &e[i].prod) > 0)
        {
            if (fscanf(in, "%u", &e[i].cost) <= 0)
                return -1;
            else
            {
                if (first == 1)
                {
                    mincost = maxcost = &e[i];
                    first = 0;
                }
                else
                {
                    f = mincost;
                    while ((f->nextval) && (f->nextval->cost < e[i].cost))
                        f = f->nextval;
                    if (e[i].cost > maxcost->cost)
                        maxcost = &e[i];
                    if (e[i].cost < mincost->cost)
                    {
                        mincost = &e[i];
                        mincost->nextval = f;
                        f->prevval = mincost;
                    }
                    else
                    {
                        e[i].nextval = f->nextval;
                        if (f->nextval)
                            f->nextval->prevval = &e[i];
                        e[i].prevval = f;
                        f->nextval = &e[i];
                    }
                }
            }
        }
        else
            return -1;
        ++i;
    }

    fclose(in);

    for (i = 0; i < ngen; ++i)
        used[i] = 0;

    for (i = 1; i <= enec; ++i)
    {
        f = mincost;
        if ((eavailable < i) && (f != 0))
        {
            //add minimal difference
            while ((f != 0) && (used[(f - e)] == 1))
                f = f->nextval;
            //printf("%d\n", ((f - e)));
            if (f)
            {
                tempcost = totalcost + f->cost;
                tempeavailable = eavailable + f->prod;
                used[(f - e)] = 1;
            }
            else
                return -1;

            //remove maximum surplus
            f = maxcost;
            while ((f != 0) && (tempcost > totalcost + 1))
            {
                if ((used[(f - e)] == 1) && (tempeavailable - f->prod >= i))
                {
                    tempeavailable = tempeavailable - f->prod;
                    tempcost = tempcost - f->cost;
                    used[(f - e)] = 0;
                }
                f = f->prevval;
            }

            //check better available in one single chunk
            f = mincost;
            while ((f) && (f->cost < totalcost + 1))
                f = f->nextval;
            while ((f->prod < i) && (f->cost <= tempcost) && (f))
                    f = f->nextval;
            if ((f) && (f->prod > i) && (f->cost <= tempcost))
            {
                totalcost = f->cost;
                eavailable = f->prod;
                for (j = 0; j < ngen; ++j)
                    used[j] = 0;
                used[(f - e)] = 1;
            }
            else
            {
                totalcost = tempcost;
                eavailable = tempeavailable;
            }

        }
        if (!f)
            return -1;
    }

    return totalcost;
}


int main()
{
    FILE *out;
    out = fopen("energii.out", "w");
    if (out)
    {
        int result = dinprog();
        fprintf(out, "%d", result);
        fclose(out);
    }
}