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

#define FILE_NOT_FOUND -1
#define NOT_ENOUGH_MEMORY -2

typedef struct _gutuie
{
    int inaltime;
    int greutate;
}
gutuie;

void myError(int code)
{
	switch(code)
	{
		case NOT_ENOUGH_MEMORY:
								printf("Nu am putut face alocarea\n");
								exit(0);
		case FILE_NOT_FOUND:
								printf("Fisierul nu a putut fi deschis\n");
								exit(0);
	}
}

int citire(gutuie **gutui, int *n, int *h, int *u)
{
    int i;//N (numarul de gutui din copac), H (inaltimea maxima la care ajunge Gigel) si U (cu cat se ridica crengile copacului dupa culegerea unei gutui).
    gutuie *temp;
    FILE *f = fopen("gutui.in", "rt");

    if(f == NULL)
        myError(FILE_NOT_FOUND);

    fscanf(f, "%i", n);
    fscanf(f, "%i", h);
    fscanf(f, "%i", u);
    temp = (gutuie*)calloc(*n, sizeof(gutuie));

    if(temp == NULL)
        myError(NOT_ENOUGH_MEMORY);

    //Pe urmatoarele N linii se afla cate 2 numere intregi reprezentand inaltimiile si greutatile gutuilor din copac.
    for(i = 0; i < *n; ++i)
    {
        fscanf(f, "%i", &temp[i].inaltime);
        fscanf(f, "%i", &temp[i].greutate);
    }

    fclose(f);
    *gutui = temp;

    return 1;
}

int scriere(gutuie* gutui, int n, int h, int u)
{
    int i;

    printf("N (numarul de gutui din copac): %i\n", n);
    printf("H (inaltimea maxima la care ajunge Gigel): %i\n", h);
    printf("U (cu cat se ridica crengile copacului dupa culegerea unei gutui): %i\n", u);

    for(i = 0; i < n; ++i)
    {
        printf("{%i %i %i}\n", i, gutui[i].inaltime, gutui[i].greutate);
    }
}
void insertion_sort(int *sir_sortat, int element, int lungime)
{
    int i;

    if(lungime == 0)
        sir_sortat[0] = element;
    else
    {
        for(i = lungime-1; i >= 0; --i)
            if(element > sir_sortat[i])
            {
                sir_sortat[i+1] = element;
                return;
            }
            else
                sir_sortat[i+1] = sir_sortat[i];

        sir_sortat[0] = element;
    }
}

void insertion_sort_g(int *sir_sortat, int inaltime, int lungime, int greutate, gutuie* gutui_sortat_inaltime)
{
    int i;

    if(lungime == 0){
        sir_sortat[0] = inaltime;
        gutui_sortat_inaltime[0].greutate = greutate;
        gutui_sortat_inaltime[0].inaltime = inaltime;
    }
    else
    {
        for(i = lungime-1; i >= 0; --i)
            if(inaltime < sir_sortat[i])
            {
                sir_sortat[i+1] = inaltime;
                gutui_sortat_inaltime[i+1].greutate = greutate;
                gutui_sortat_inaltime[i+1].inaltime = inaltime;
                return;
            }
            else{
                sir_sortat[i+1] = sir_sortat[i];
                gutui_sortat_inaltime[i+1].greutate = gutui_sortat_inaltime[i].greutate;
                gutui_sortat_inaltime[i+1].inaltime = gutui_sortat_inaltime[i].inaltime;
            }
        gutui_sortat_inaltime[0].greutate = greutate;
        gutui_sortat_inaltime[0].inaltime = inaltime;
        sir_sortat[0] = inaltime;
    }
}
//pun elemente in coada pana nu mai am loc
//daca urmatorul element pe care il gasesc este mai mare decat primul cel mai mic element din coada il bag in locul lui
int gutui_gmax(gutuie* gutui, int n, int h, int u)
{
    int i, j, k, *gutui_sortat, *gutui_sortat_temp, pornire = 0, pornire_prec = 0, temp, intra = 0, poz_insert = 0, sum = 0;
    gutuie *gutui_sortat_inaltime;
    //N (numarul de gutui din copac)
    //H (inaltimea maxima la care ajunge Gigel)
    //U (cu cat se ridica crengile copacului dupa culegerea unei gutui)

    gutui_sortat = (int*)calloc(n + 1, sizeof(int));
    gutui_sortat_temp = (int*)calloc(n, sizeof(int));
    gutui_sortat_inaltime = (gutuie*)calloc(n, sizeof(gutuie));
    //intai sortez gutuile dupa inaltime
    for(i = 0; i < n; ++i)
        insertion_sort_g(gutui_sortat_temp, gutui[i].inaltime, i, gutui[i].greutate, gutui_sortat_inaltime);
    //printf("Sortate pe inaltime:\n");
    //for(i = 0; i < n; ++i){
    //    printf("{%i %i}\n", gutui_sortat_inaltime[i].inaltime, gutui_sortat_inaltime[i].greutate);
    //}
    //printf("\n");
    pornire = 0;
    poz_insert = 0;//defapt e lungme sir sortat
    gutui_sortat[poz_insert++] = gutui_sortat_inaltime[0].greutate;
    for(i = 0; i < n;)
    {
        temp = 0;
        intra = 0;
        j = 0;
        while(j + i + 1 < n)//trebuie sa ma gandesc si la ultima gutuie
        {
            //printf("{1 %i %i}",h - u,gutui_sortat_inaltime[i + j + 1].inaltime);
            if(h - u < gutui_sortat_inaltime[i + j + 1].inaltime)//cu asta ia toate gutuile care numai pot fi ajunse daca ia una singura de pe nivelul asta
            {
                if(j == 0 && i != 0)
                    insertion_sort(gutui_sortat, gutui_sortat_inaltime[i + j].greutate, poz_insert++);

                if(gutui_sortat_inaltime[i + j + 1].greutate > gutui_sortat[pornire])//daca gutuia luata este mai mare decat prima gutuie din serie atunci o inlocuieste
                {
                    insertion_sort(gutui_sortat, gutui_sortat_inaltime[i + j + 1].greutate, poz_insert++);
                    ++pornire;
                    ++intra;
                    /*printf("rezultat %i:", pornire);
                    for(k = pornire; k < poz_insert; ++k){
                        printf("%i ", gutui_sortat[k]);
                    }
                    printf("\n");*/
                }
                else
                    temp++;
            }
            else
                break;
            ++j;
        }
        if(intra > 0)
            h = h - intra *  u + u;
        if(temp == 0 && intra == 0)
            if(i != 0)
                insertion_sort(gutui_sortat, gutui_sortat_inaltime[i].greutate, poz_insert++);

        h = h - u;
        i = i + j + 1;
    }
    insertion_sort(gutui_sortat, 0, poz_insert++);//mai inserez una ca imi baga ceva in plus
    //printf("\nRezultat %i:", pornire);
    for(i = pornire; i < poz_insert; ++i){
        //printf("%i ", gutui_sortat[i]);
        sum += gutui_sortat[i];
    }
    //printf("\nsuma: %i ", sum);
    FILE *f = fopen( "gutui.out", "wt");

    fprintf( f, "%i ", sum);

    free(gutui_sortat);
    free(gutui_sortat_temp);
    free(gutui_sortat_inaltime);
    return 1;
}

int main()
{
    gutuie *gutui;
    int i, n, h, u;

    citire(&gutui, &n, &h, &u);

    //scriere(gutui, n, h, u);

    gutui_gmax(gutui, n, h, u);
    //eliberare gutui
    free(gutui);

    return 0;
}