/* gutui.c*/

#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;   
               
} Tgutuie, *Agutuie;

Tgutuie  gutui[100000];
int mergeaux[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"); 
  
     /* H (inaltimea maxima la care ajunge Gigel)*/ 
     
     copiat=fscanf(file_in, "%i",&H);
     if(!copiat)  fatal("eroare la citire H din fisier"); 
   
      /*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"); 
   
     
     int i,g,h;
     int j=0;
     for(i=0;i<N;i++){
     
            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[j].inaltime=(H-h)/U+1;
            gutui[j].greutate=g;
            j++;
            }
                                  
     }
     n=j;
     fclose(file_in);
       
}



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 void AfisareGutui(Agutuie g, int n)

{

int i=0;
printf("\n------\n");
while(i<n){

printf("%i %i\n",g->inaltime,g->greutate);

g++;

i++;

}
printf("\n------\n");
}

static void Afisare(int* g, int n)

{

int i=0;
printf("\n------\n");
while(i<n){

printf("%i\n",*g);

g++;

i++;

}
printf("\n------\n");
}*/
static int merge (Agutuie p, int lp, Agutuie q,int lq)
{
    int i=0;
    int j=0;
    int k=0;
    Agutuie aux=p;
    while(i<lp&&j<lq&&k<aux->inaltime)
        if (aux->greutate >= q->greutate){
                 mergeaux[k]=aux->greutate;
                 aux++;
                 i++;
                 k++;            
              }
        else{
                 mergeaux[k]=q->greutate;
                 q++;
                 j++;
                 k++;            
              }
    while(i<lp&&k<p->inaltime){
                 mergeaux[k]=aux->greutate;
                 aux++;
                 i++;
                 k++;            
              }
             
    while(j<lq&&k<p->inaltime){
                 mergeaux[k]=q->greutate;
                 q++;
                 j++;
                 k++;            
              }
    
    k= MIN(lp+lq,p->inaltime);
  
    return k;
    
}
static int alegere_gutui(Agutuie gutui)
{
 
 
 qsort (gutui, n, sizeof(Tgutuie), compare_by_height_and_weight);
 //AfisareGutui(gutui,n);
   
 long greutate=0;
 Agutuie p,q,aux;
 int i,k,lp;
 int limita_categorie;
 int diferenta_categorie;
 int inaltimea_categoriep;
 int lungime_catp_utila;
 int lungime_catq_utila;
 //pregatire date pas initial
 p=gutui;
 q=gutui;
 while(q->inaltime==p->inaltime&& q-gutui<n) q++;
 diferenta_categorie=(p->inaltime-q->inaltime);
 while(q-gutui<n){
         
         //fructe ce vor fi culese 
         inaltimea_categoriep=p->inaltime;
         for(i=0;i<MIN(diferenta_categorie,p->inaltime)&&p<q&&q-gutui<n;i++){
             greutate+=p->greutate;
            // printf("%i+",p->greutate);
             p++;
         }
        
         
         
        //pregatirea date pentru pasul urmator
         aux=p;
         while(aux<q && aux-p < q->inaltime) {aux->inaltime=q->inaltime;  aux++;} 
         lungime_catp_utila=aux-p;
         
         //AfisareGutui(gutui,n);
         
         aux=q; 
         while(q->inaltime==p->inaltime&& q-gutui<n&& (q-aux)<p->inaltime) q++;
         lungime_catq_utila=q-aux;
         
        
         qsort (p, q-p, sizeof(Tgutuie), compare_by_height_and_weight);
         //daca au mai ramas fructe din prima categorie cu inalimea p->inaltime
         //interclasam elementele in functie de greutate si modifica inalimea  
         //altfel nu inteclasam si p devine automat urmatoarea categorie
         /*if(p!=aux)  {
                     //printf("dupa sortare:%i %i %i si %i %i %i ",p->inaltime,p->greutate,lungime_catp_utila,aux->inaltime,aux->greutate,lungime_catq_utila);
                     k=merge(p,lungime_catp_utila,aux,lungime_catq_utila);
                    // AfisareGutui(gutui,n);
                        i=0;
                        aux=p;
                        while(i<k){
                           aux->greutate=mergeaux[i];
                           aux++;
                           i++;           
                        }
                      //printf("dupa merger");
                      //Afisare(mergeaux,k);
                      //AfisareGutui(gutui,n);
                     }
                     
         //trecem la urmatoarea categorie*/
         while(q->inaltime==p->inaltime&& q-gutui<n) q++;
        
        
        
         
      
 }
 //culegerea ultimelor fructe
 k=p->inaltime;
 for(i=0;i<k;i++){
             greutate+=p->greutate;
            // printf("%i+",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);
    //getchar();
    return 0;
}