#include <stdlib.h>
#include <stdio.h>
#include <math.h>
//#include <conio.h>

typedef struct gutuie {
        unsigned long H_gut;    // intaltimea la care se afla gutuia
        unsigned long G_gut;    // greutatea gutuiei
        unsigned long prioritate;  // prioritatea culegerii gutuiei = nivel - 1
                                   // prioritate 0 => gutuia trebuie culeasa imediat
        } ;
        
/* OBS: 
 * - se va lucra doar cu primele x (< toleranta) gutui din vectorul de gutui sortat descrescator dupa greutate
 * - dintre acestea de mai sus se vor selecta secvential gutuile de prioritate < toleranta (=nr maxim de gutui
 * ce pot fi culese inainte ca  index_min sa depaseasca H)
 */
 
void read_const (FILE* in, unsigned long *N, unsigned long *H, unsigned long *U) // citeste N,H,U
{ fscanf(in, "%lu", N);
  fscanf(in, "%lu", H);
  fscanf(in, "%lu", U);
  // DEBUG purposes:
  //printf("Gutui in copac: %lu \n", *N);
  //printf("Inaltime Gigel: %lu \n", *H);
  //printf("Rata de inaltare: %lu \n", *U);
}

void read_gut (FILE *in, gutuie *gutui, unsigned long N) // citeste gutuile si le salveaza intr-un vector
{ for (int i=0; i<N; i++) 
  { fscanf (in, "%lu", &gutui[i].H_gut);
    fscanf (in, "%lu", &gutui[i].G_gut);
    // DEBUG purposes:
    //printf("Gutuia %i > %lum %lukg\n", i+1, gutui[i].H_gut, gutui[i].G_gut);
  }
}

void set_prioritate (gutuie *gutui, unsigned long N, unsigned long U, unsigned long H, unsigned long *index_max, unsigned long *index_min) 
{ unsigned long niv;
  for (int i=0; i<N; i++) 
  { niv = (unsigned long)floor(gutui[i].H_gut / U);
    gutui[i].prioritate = (unsigned long)floor( (H-gutui[i].H_gut) / U);
    if (niv>*index_max)
       *index_max = niv;
    if (niv<*index_min)
       *index_min=niv;
    // DEBUG purposes:
    //printf("Gutuia %i > CONTROL %lu \n", i+1, gutui[i].H_gut / U);
    //printf("Gutuia %i > prioritate %lu\n", i+1, gutui[i].prioritate);
  }
}

void print_gutui (gutuie *gutui, unsigned long N) 
{ printf("Format:\n\tGutuia nrcrt > \tH_gut \tG_gut \t[prioritate]\n");
  for (int i=0; i<N; i++) 
    printf("\tGutuia %i > \t%lum \t%lukg \t[%lu]\n", i+1, gutui[i].H_gut, gutui[i].G_gut, gutui[i].prioritate);
}

int compare (const void *g1, const void *g2) // pt sortate descrescatoare dupa greutate
{ 
  return (int)((*(gutuie*)g2).G_gut - (*(gutuie*)g1).G_gut);
} 

int compare_priori (const void *g1, const void *g2) // pt sortate crescatoare dupa prioritate
{ 
  if (((*(gutuie*)g1).prioritate - (*(gutuie*)g2).prioritate) == 0) // in caz de egalitate
     return (int)((*(gutuie*)g2).G_gut - (*(gutuie*)g1).G_gut);     // alege gutuia de greutate mai mare
  return (int)((*(gutuie*)g2).prioritate - (*(gutuie*)g1).prioritate);
} 

void truncate (gutuie *vechi, gutuie *nou, unsigned long toleranta)
{ for (int i=0; i<toleranta; i++) 
     nou[i]=vechi[i];
}

void sum (gutuie *gutui_best, unsigned long n)
{ unsigned long sum = 0;
  for (int i=0; i<n; i++)
      sum+=gutui_best[i].G_gut;
  FILE *out = fopen ("gutui.out", "wt");
  fprintf(out, "%lu",sum);
  fclose(out);
  // DEBUG purposes:
  //printf("Suma maxima: %lu",sum);
}

int main() 
{ unsigned long N;    // numarul de gutui din copac
  unsigned long H;    // inaltime maxima Gigel
  unsigned long U;    // rata de inaltare a gutuilor
  //unsigned long Gmax; // greutatea maxima culeasa de Gigel 
  unsigned long index_max=0;      // nivelul MAXIM al sirului de gutui accesibile (cele mai de SUS gutui la care poate ajunge Gigel)
  unsigned long index_min=(unsigned long)pow(2,sizeof(long)-1);      // nivelul MAXIM al sirului de gutui accesibile (cele mai de JOS gutui la care poate ajunge Gigel)
  // nivel = inaltime_gutuie % rata_intaltare
  unsigned long niv_max;         // = H / U
  unsigned long toleranta;       // numarul maxim de gutui pe care le pot culege inainte de a depasi H
  FILE* in = NULL;
  in = fopen("gutui.in","rt");
  if (!in)
     printf("Error opening file\n");
  read_const (in,&N,&H,&U);
  gutuie gutui[N];
  read_gut (in,gutui,N);
  fclose(in);
  set_prioritate(gutui,N,U,H,&index_max,&index_min);
  niv_max = (unsigned long)floor(H/U);
  toleranta = niv_max - index_min;
  //printf("Index maxim: %lu\nIndex minim: %lu\nToleranta: %lu\n", index_max, index_min, toleranta);
  //printf("Compare: %i\n", compare(&gutui[0],&gutui[1]));
  qsort (gutui, N, sizeof(gutuie), compare);
  //print_gutui (gutui,N);
  if (toleranta<N)
     { gutuie gutui_best[toleranta];
       truncate (gutui, gutui_best, toleranta);
       sum(gutui_best,toleranta);
      }
  else
      sum(gutui,N);
  
  //getch();
  return 0;
}