/* gutui.c*/
/*
Gutui
Gigel are in curte un gutui. El se hotaraste sa culeaga cat mai multe gutui, 
dar are o problema: copacul este atat de incarcat cu fructe incat la fiecare
 gutuie culeasa, toate crengile acestuia se ridica in inaltime cu fix U centimetrii.
  Din pacate Gigel nu are scara la el si nu poate sa culeaga gutui la o inaltime
   mai mare de H centimetrii.

Nici de aceasta data Gigel nu se descurca singur. Ajutati-l sa culeaga cat mai
 multe gutui.

Stiind greutatea si inaltimea initiala a fiecarui fruct, se cere cea mai mare 
recolta de gutui pe care o poate aduce Gigel acasa. Cum se gandeste sa le vanda
 in piata, il intereseaza o greutate cat mai mare, nu un numar cat mai mare.



Date de iesire
In fisierul de iesire gutui.out trebuie scrisa greutatea maxima a gutuilor pe 
care le poate culege Gigel.

Restrictii
1 = N = 100000
H, U, greutatea maxima culeasa de Gigel, greutatile si inaltimile gutuilor
 sunt < 231
O solutie O(N2) obtine ~80% din teste.
*/


/*
Date de intrare
Pe prima linie a fisierului de intrare gutui.in se afla 3 numere intregi: 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).
Pe urmatoarele N linii se afla cate 2 numere intregi reprezentand inaltimiile 
si greutatile gutuilor din copac.
*/


#include <unistd.h> /* pentru open(), exit() */
#include <errno.h> /* perror() */
#include <stdlib.h>
#include <stdio.h>


#define INF 32000
#define MAX(a,b) ((a)>(b) ? (a) : (b))
#define MIN(a,b) ((a)<(b) ? (a) : (b))

void fatal(char * mesaj_eroare)
{
     perror(mesaj_eroare);
     exit(1);
}

typedef struct gutuia {
                int greutate;     
                int inaltime;   
              //  ...                  /* other things to be added later */
               
} Tgutuie, *Agutuie;

Tgutuie  gutui[100000];
int N,H,U;
int n;


static void ReadFile()
{
     FILE *file_in= fopen("gutui.in", "r");
     int copiat;
     /*citim N (numarul de gutui din copac)*/
     if(!file_in) printf("avem o mare problema\n");
   
     copiat=fscanf(file_in, "%i",&N);
     if(!copiat)  fatal("eroare la citire N din fisier"); 
     fgetc(file_in);
     /* H (inaltimea maxima la care ajunge Gigel)*/ 
     
     copiat=fscanf(file_in, "%i",&H);
     if(!copiat)  fatal("eroare la citire H din fisier"); 
     fgetc(file_in);
      /*U  (cu cat se ridica crengile copacului dupa culegerea unei gutui)*/
     copiat=fscanf(file_in, "%i",&U);
     if(!copiat)  fatal("eroare la citire U din fisier"); 
     fgetc(file_in); 
     
     int i,g,h;
     for(i=0;i<N;){
     
            copiat=fscanf(file_in, "%i",&h);
            if(!copiat)  fatal("eroare la citire inaltime din fisier");
            copiat=fscanf(file_in, "%i",&g);
            if(!copiat)  fatal("eroare la citire greutate din fisier");
            if((H-h)/U+1>0)
            {
            gutui[i].inaltime=(H-h)/U+1;
            gutui[i].greutate=g;
            i++;
            }
                                  
     }
     n=i;
     fclose(file_in);
       
}

static void AfisareGutui(Agutuie g, int n)
{
     int i=0;
     while(i<n){
           printf("%i %i\n",g->inaltime,g->greutate);
           g++;
           i++;
     }
}
int compare_by_height_and_weight (const void * a, const void * b)
{
  if(((Tgutuie *)b)->inaltime == ((Tgutuie *)a)->inaltime)
  return ( ((Tgutuie *)b)->greutate - ((Tgutuie *)a)->greutate );
  return ( ((Tgutuie *)b)->inaltime - ((Tgutuie *)a)->inaltime );
}



static int alegere_gutui(Agutuie gutui)
{
 
 qsort (gutui, n, sizeof(Tgutuie), compare_by_height_and_weight);  
 long greutate=0;
 Agutuie p,q,aux;
 int i;
 
 //pregatire date pas initial
 p=gutui;
 q=gutui;
 while(q->inaltime==p->inaltime&& q-gutui<n) q++;
 
 while(q-gutui<n){
         
         //fructe ce vor fi culese 
         for(i=0;i<(p->inaltime-q->inaltime);i++){
             greutate+=p->greutate;
             p++;
         }
         aux=p;
        
        //pregatirea date pentru pasul urmator
         
         while(aux<q) {aux->inaltime=q->inaltime; printf("%i?",q-gutui); aux++;}         
         while(q->inaltime==p->inaltime&& q-gutui<n) q++;
         qsort (p, q-p, sizeof(Tgutuie), compare_by_height_and_weight);
        
         
         
      
 }
 //culegerea ultimelor fructe
 for(i=0;i<p->inaltime;i++){
             greutate+=p->greutate;
             p++;
 }

 return greutate; 
 
 
}

int main(void)
{
    ReadFile();
    FILE *file_out= fopen("gutui.out", "w");
    fprintf(file_out,"%i\n",alegere_gutui(gutui));
    fclose(file_out);
    return 0;
}