#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 \t\tG_gut \t\t[prioritate]\n");
  for (int i=0; i<N; i++) 
    printf("\tGutuia %i > \t%lum \t\t%lukg \t\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*)g1).prioritate - (*(gutuie*)g2).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;
  FILE *out = fopen ("gutui.out", "wt");
  for (int i=0; i<n; i++)
  { sum+=gutui_best[i].G_gut;
    //printf("\tGutuia %i > \t%lum \t%lukg \t[%lu]\n", i+1, gutui_best[i].H_gut, gutui_best[i].G_gut, gutui_best[i].prioritate);
   }
  fprintf(out, "%lu",sum);
  fclose(out);
  // DEBUG purposes:
  printf("Suma maxima: %lu\n",sum);
}
*/

// returneaza numarul de gutui ramase cu greutatea mai mare decat gutuia curenta (aflata la index)
unsigned long count (gutuie *gutui, unsigned long index, unsigned long N) // complexitate: O(n)
{ unsigned long overflow=0;
  if (index == N-1)
     return 0;
  for (int i=index+1; i<N; i++) 
    if (gutui[i].G_gut > gutui[index].G_gut)
       overflow++;
  return overflow;
}
/*
// euristica pentru aplicarea functiei count:
// se aplica count doar daca gutuia curenta este mai grea decat ultima gutuie (ref) pe care s-a aplicat count
bool test (gutuie *ref, gutuie current) 
{ if (ref!=NULL)
     if (ref->G_gut <= current.G_gut) {printf("true\n");
        return true; }
     else { printf("false\n");
        return false; }
  else
     { *ref = current;
       printf ("null true\n");
       return true; 
     }
} 
*/
void sum (gutuie *gutui, unsigned long N, unsigned long *steps_possible, unsigned long *offset, unsigned long *suma)
{ for (int i=0; i<N && steps_possible >= 0; i++)
  { printf("test prioritate: %4.0lf\n",(double)(gutui[i].prioritate) - (double)*offset);
    printf("control offset: %4.0lf\n",(double)*offset);
    printf("control steps: %lu\n",*steps_possible);
    printf("control count: %lu\n",count(gutui,i,N));
    if ( ((double)(gutui[i].prioritate) - (double)*offset >= 0) && (count(gutui,i,N) < *steps_possible) )
       { printf ("Selected: \t%lukg %lum\n", gutui[i].G_gut, gutui[i].H_gut);
         *suma += gutui[i].G_gut;
         (*offset)=(*offset)+1;
         //printf("control2 offset: %lf\n",(double)*offset);
         (*steps_possible)=(*steps_possible)-1;
       } 
  }
}

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=0; // 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
  unsigned long offset=0;
  FILE* in = NULL;
  in = fopen("gutui.in","rt");
  if (!in)
     { printf("Error opening input file\n");
       return 1;
       }
  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_priori);
  print_gutui (gutui,N);
  sum (gutui, N, &toleranta, &offset, &Gmax);
  printf("Suma maxima: %lu\n", Gmax);
  FILE *out = fopen ("gutui.out", "wt");
  if (!out)
     { printf("Error opening output file\n");
       return 2;
       }

  //printf("Valori mai mari decat %lu: %lu", gutui[0].G_gut, count(gutui,0,N));
/*  if (toleranta<N)
     { gutuie gutui_best[toleranta];
       truncate (gutui, gutui_best, toleranta);
       sum(gutui_best,toleranta);
      }
  else
      sum(gutui,N);
*/
  fprintf (out, "%lu", Gmax);
  
  fclose(out);
  //printf("------------------\n");
  
  getch();
  return 0;
}