/* Stefan-Dobrin Cosmin
 * 321CA
 *
 * Proiectarea Algoritmilor - Tema 1
 *
 * Problema 2: Gutui
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

#define FINNAME "gutui.in"
#define FOUTNAME "gutui.out"

typedef unsigned U32;

typedef struct{
    U32 g;
    U32 h;
} Gutuie;

typedef Gutuie TipData;

/******************************************************************************
 ***************************** Header HEAP ************************************
 ******************************************************************************/
struct heap{
	TipData *values;
	int cap;    //capacitate
	int dim;   //dimensiune
};

typedef struct heap *Heap;

/*Functie care compara doua elemente ale heap-ului*/
typedef int (*PFC)(TipData, TipData); //pointer la functie

/*Creeaza un heap de capacitate maxima 'cap'*/
Heap H_New(int cap);

/*Sterge un heap*/
void H_Delete(Heap h);

/*Coboara valoarea de pe pozitia 'poz' in heap.*/
void H_CobVal(Heap H, int poz,PFC H_Compare);

/*Urca valoarea de pe pozitia 'poz' in heap.*/
void H_UrcVal(Heap h,int poz,PFC H_Compare);

/*Obtine elementul minim din heap.*/
TipData H_Min(Heap h);

/*Extrage si elimina elementul minim din heap.*/
TipData H_GetMin(Heap h,PFC H_Compare);

/*Adauga un element intr-un heap*/
void H_Add(Heap h,TipData val,PFC H_Compare);

/*Inlocuim valoarea minima din heap*/
void H_ReplaceMin(Heap h, TipData val, PFC H_Compare);

/*Construieste un heap pornind de la un vector 'val' dat de marime 'size' .*/
void H_Construieste(Heap h, TipData *val,int size,PFC H_Compare);

/*Returneaza numarul de elemente al unui heap*/
int H_Size(Heap h);


/******************************************************************************
 ******************* Implementare HEAP ************************************
 *****************************************************************************/

/*Creeaza un heap de capacitate maxima 'cap'*/
Heap H_New(int cap)
{
	Heap h;
	h=(Heap)calloc(1,sizeof(struct heap));
	h->cap=cap;
	h->values=(TipData*)calloc(cap,sizeof(TipData));
	return h;
}

/*Sterge un heap*/
void H_Delete(Heap h)
{
	free(h->values);
	free(h);
}

/*Returneaza indicele parintelui lui 'poz' sau -1 in cazul in care nu exista*/
int H_P(Heap h, int poz){
	assert(poz < h->cap);
	if(poz==0)
		return -1;
	return (poz-1)/2;
}

/*Returneaza indicele descendentului stanga al lui 'poz', sau -1 in cazul in care nu exista*/
int H_DS(Heap h, int poz){
	assert(poz < h->cap);
	if(2*poz+1 >= h->dim) return -1;
	return 2*poz+1;
}
/*Returneaza indicele descendentului dreapta al lui 'poz', sau -1 in cazul in care nu exista*/
int H_DD(Heap h, int poz){
	assert(poz < h->cap);
	if(2*poz+2 >= h->dim) return -1;
	return 2*poz+2;
}

/*Coboara valoarea de pe pozitia 'poz' in heap.*/
void H_CobVal(Heap H, int poz,PFC H_Compare)
{
    TipData valmin;
    int pozDesc=0;
    for (;;) {
        // Se verifica daca ambii descendenti exista
        if(H_DD(H,poz)==-1 && H_DS(H,poz)==-1)
        	return ;
        valmin=H->values[poz];
        //Daca minimul e mai mare ca descendentul drept
        if(H_DD(H,poz)>=0 && H_Compare(H->values[H_DD(H,poz)],valmin)<0)
        	valmin=H->values[H_DD(H,poz)];

        //Daca minimul e mai mare ca descendentul stang
        if(H_DS(H,poz)>=0 && H_Compare(H->values[H_DS(H,poz)],valmin)<0)
        	valmin=H->values[H_DS(H,poz)];

        if (H_Compare(valmin,H->values[poz])==0)
        	return; // Nu e nimic de facut aici
        //Daca minimul e descendentul stang
        if (H_DS(H,poz)>=0 && H_Compare(valmin , H->values[H_DS(H,poz)])==0)
            pozDesc = H_DS(H,poz);
        //Daca minimul e descendentul drept
        if (H_DD(H,poz)>=0 && H_Compare(valmin , H->values[H_DD(H,poz)])==0)
            pozDesc = H_DD(H,poz);
        //Interschimbam
        TipData aux=H->values[poz];
        H->values[poz]=H->values[pozDesc];
        H->values[pozDesc]=aux;
        poz = pozDesc;
    }
}

/*Urca valoarea de pe pozitia 'poz' in heap.*/
void H_UrcVal(Heap h,int poz,PFC H_Compare)
{
    // Cat timp parintele exista si are o valoare mai mare decat nodul curent...
    while (poz > 0 && H_Compare(h->values[poz] , h->values[H_P(h,poz)])<0)
    {
         // ... interschimbam nodul curent cu parintele
        TipData aux=h->values[poz];
        h->values[poz]=h->values[H_P(h,poz)];
        h->values[H_P(h,poz)]=aux;
        // Urcam pozitia curenta mai sus cu un nivel si reluam
        poz = H_P(h,poz);
    }
}

/*Returneaza numarul de elemente al unui heap*/
int H_Size(Heap h)
{
    return h->dim;
}

/*Obtine elementul minim din heap.*/
inline TipData H_Min(Heap h)
{
	return h->values[0];
}

/*Extrage si elimina elementul minim din heap.*/
TipData H_GetMin(Heap h,PFC H_Compare)
{
	//Memoram minimul
	TipData min=H_Min(h);

	//Interschimbam cu ultimul element
	TipData aux=h->values[0];
	h->values[0]=h->values[h->dim-1];
	h->values[h->dim-1]=aux;
	//Scadem marimea;
	h->dim=h->dim-1;
	//Rearanjam heap-ul;
	H_CobVal(h,0,H_Compare);
	return min;
}

/*Adauga un element intr-un heap*/
void H_Add(Heap h,TipData val,PFC H_Compare)
{
	//Daca am depasit marimea, realocam
	if(h->dim==h->cap)
		{
			h->values=realloc(h->values,(1+2*(h->cap))*sizeof(TipData));
			h->cap=2*(h->cap)+1;
		}
	//Introducem noua valoare pe ultima pozitie in heap
	h->dim=h->dim+1;
	h->values[h->dim-1]=val;
	//Rearanjam heap-ul
	H_UrcVal(h,h->dim-1,H_Compare);
}

void H_ReplaceMin(Heap h, TipData val, PFC H_Compare)
{
    //Inlocuim valoarea minima
    h->values[0]=val;
    //Rearanjam heap-ul
    H_CobVal(h,0,H_Compare);
}



/******************************************************************************
 ******************* END Implementare HEAP ************************************
 *****************************************************************************/


U32 H;
U32 U;
int n;
Gutuie *gut;

/*Functia de comparare a doua gutui, folosita pentru Heap;*/
int comparaH(TipData e1,TipData e2)
{
    return e1.g-e2.g;
}

int comparator(void* e1, void* e2)
{
    Gutuie* a=(Gutuie*)e1;
    Gutuie* b=(Gutuie*)e2;

    if( (H - a->h)/U < (H - b->h)/U)      //daca prima se afla intr-o zona mai ridicata
        return -1;
    else
        if((H - a->h)/U > (H - b->h)/U)   //daca prima se afla intr-o zona mai joasa
            return 1;
        else                            //daca se afla in aceeasi zona
            return  b->g - a->g;        //sortam invers dupa greutate
    
}


/* Functia realizeaza citirea datelor de intrare din fisierul FINNAME in vectoriul de gutui 'gut'
 * intoarce numarul de gutui;
 */
int readInput()
{
    FILE *fin=fopen(FINNAME,"r");
    int i;

    //Citim numarul de linii/coloanes
    fscanf(fin,"%d %u %u",&n,&H,&U);

    //Alocam spatiu
    gut=(Gutuie*)calloc(n,sizeof(Gutuie));
    

    //Citim greutatile si inaltimile pomilor
    for(i=0;i<n;i++)
        fscanf(fin,"%u %u",&gut[i].h,&gut[i].g);

    fclose(fin);

    return n;
}


/*Obtine pozitia gutuiei cu cea mai mica greutate dintre gutuile cu index-ul 0..n din vectorul 'vec'.*/
int getMinPoz(Gutuie *vec,int n)
{
    int i;
    //Intoarcem -1 daca vectorul e gol(
    if(n<0)
        return -1;

    int minpoz=0;
    Gutuie min=vec[0];

    //Obtinem pozitia minima
    for(i=1;i<=n;i++)
        if(min.g > vec[i].g)
            min=vec[i], minpoz=i;

    return minpoz;
}

//Intoarce zona (intre 0 si zona maxima) in care se afla gutuia g
inline int getZona(Gutuie g)
{
    return (H-g.h)/U;
}

/* Primeste ca parametru vectorul in care e construita solutia si numarul de Pasi;*/
void getSolutie(Heap solutie,int nrPasi)
{
    /*Dupa k pasi, in solutie[i] se va afla a i-a gutuie ce este aleasa ca facand parte din solutie,
     *considerand ca avem doar gutuile din primele k zone;*/
    int i;
    int poz=0;
    Gutuie zero;
    zero.g=0;
    zero.h=0;

    for(i=0;i<nrPasi;i++)
    {
        //Alegem pe pozitia curenta cea mai mare gutuie (prima conform sortarii) din zona curenta, daca exista
        if(getZona(gut[poz])==i)
        {
            H_Add(solutie,gut[poz++],&comparaH);
        }
        else
            H_Add(solutie,zero,&comparaH);
        //Cat timp gutuia curenta este in zona curenta si ea are o greutate mai mare decat minimul curent
        while(poz<n && getZona (gut[poz])==i && gut[poz].g > H_Min(solutie).g)
        {
            //inlocuim minimul in vectorul solutie
            H_ReplaceMin(solutie,gut[poz++],&comparaH);
        }
        //ignoram restul gutuilor din zona curenta
        while(poz<n && getZona (gut[poz])==i)
                poz++;
    }
}



int main()
{
    int i;

    //Citim datele de intrare
    readInput();

    /* Sortam gutuile astfel incat zonele (de dimensiune U) sa se afle in ordine crescatoare
     * iar gutuile din aceeasi zona sa se afle in ordine descrescatoare in fct de greutate;*/
    qsort((void*)gut,n,sizeof(Gutuie),(__compar_fn_t)&comparator);

    //Numarul de gutui alese
    int nrZone=(H - gut[n-1].h)/U+1;     //Zona cea mai joasa

    //Afisare informatii
    printf("%d\n",nrZone);
    for(i=0;i<n;i++)
        printf("%u - %u\n",gut[i].h,gut[i].g);


    //Alocam spatiu pentru solutie
    Heap solutie=H_New(nrZone);

    //Obtinem vectorul solutie
    getSolutie(solutie,nrZone);

    //Calculam greutatea maxima
    int sum=0;
    printf("Solutie:\n");
    for(i=0;i<nrZone;i++)
    {
        printf("%u - %u\n",H_Min(solutie).h,H_Min(solutie).g);
        sum+=H_GetMin(solutie,&comparaH).g;
    }
    

    printf("Greutate maxima: %u\n",sum);

    //Eliberam memoria folosita de vectori
    free(gut);
    free(solutie);

    //Scriem solutia in fisierul de iesire
    FILE *fout=fopen(FOUTNAME,"w");
    fprintf(fout,"%u",sum);
    fclose(fout);

    return 0;
}


/*                  ****************          *****            ***          *******
 *                  ****************          ******           ***          *********
 *                  ***                       *** ***          ***          ***    ****
 *                  ***                       ***  ***         ***          ***      ****
 *                  ***                       ***   ***        ***          ***       ****
 *                  ***                       ***    ***       ***          ***        ****
 *                  ****************          ***     ***      ***          ***         ****
 *                  ****************          ***      ***     ***          ***         ****
 *                  ***                       ***       ***    ***          ***         ****
 *                  ***                       ***        ***   ***          ***        ****
 *                  ***                       ***         ***  ***          ***       ****
 *                  ***                       ***          *** ***          ***     ****
 *                  ****************          ***           ******          **********
 *                  ****************          ***            *****          ********
 */