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

int comp(const gutuie *a, const gutuie *b)
{
    return -((*a).inaltime - (*b).inaltime);
}

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);
    qsort(gutui, n, sizeof(gutuie), comp);
    for(i = 0; i < n; ++i){
        gutui_sortat_inaltime[i] = gutui[i];
    }
    //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;
    for(i = 0; i < n;)
    {
        temp = 0;
        j = 1;

        if(gutui_sortat_inaltime[i].inaltime > h)
            continue;

        insertion_sort(gutui_sortat, gutui_sortat_inaltime[i].greutate, poz_insert++);
        temp++;

        while(j + i < n && gutui_sortat_inaltime[i + j].inaltime > h - u)
        {
            if(gutui_sortat_inaltime[i + j].greutate > gutui_sortat[pornire])
            {
                gutui_sortat[pornire] = 0;
                insertion_sort(gutui_sortat, gutui_sortat_inaltime[i + j].greutate, poz_insert++);
                ++pornire;

            }
            ++j;
        }

        h = h - u;


        i = i + j;
    }
    //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);
    fclose(f);
    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;
}