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

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

typedef unsigned U32;

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

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


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(Gutuie *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;
    int pozMin=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)
        {
            solutie[i]=gut[poz++];
            //si actualizam minimul
            pozMin=getMinPoz(solutie,i);
        }
        //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 > solutie[pozMin].g)
        {
            //inlocuim minimul in vectorul solutie
            solutie[pozMin]=gut[poz++];
            //si actualizam minimul;
            pozMin=getMinPoz(solutie,i);
        }
        //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("%d - %d\n",gut[i].h,gut[i].g);


    //Alocam spatiu pentru solutie
    Gutuie *solutie=(Gutuie*)calloc(nrZone,sizeof(Gutuie));

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

    //Calculam greutatea maxima
    int sum=0;
    printf("Solutie:\n");
    for(i=0;i<nrZone;i++)
    {
        printf("%d - %d\n",solutie[i].h,solutie[i].g);
        sum+=solutie[i].g;
    }

    printf("Greutate maxima: %d\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;
}


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