#include<stdio.h>
#include<stdlib.h>
typedef struct gut{
int inal, greut;
}gut;
void afisare(gut *a, int n)
{
printf("\n");
int i;
for(i =0; i< n; i++)
printf("%d Inaltime %d, Greutate %d\n", i, a[i].inal,a[i].greut);
}
int compare(const void* x,const void* y)
{
return (((gut*)x)->inal) <= (((gut*)y)->inal);
}
int h,u;
int compare1(const void* x, const void* y)
{
if(((h-(((gut*)x)->inal))/u)!=((h-(((gut*)y)->inal))/u))
if ((((gut*)x)->inal) < (((gut*)y)->inal))
return 1;
else
return -1;
else
return (((gut*)x)->greut) <= (((gut*)y)->greut);
}
int minim(int *c,int n){
int min = c[0];
int i;
for(i = 1; i <n; i++)
if(c[i] < min)
min = c[i];
return min;
}
int main()
{
FILE *f, *fo;
f = fopen("gutui.in", "r");
fo = fopen("gutui.out", "w");
int n, i, j;
gut *a = NULL;
fscanf(f, "%d", &n);
fscanf(f, "%d", &h);
fscanf(f, "%d", &u);
a = (gut*)malloc(n * sizeof(gut));
for(i = 0; i < n; i++)
{
fscanf(f, "%d", &a[i].inal);
fscanf(f, "%d", &a[i].greut);
}
qsort(a, n, sizeof(gut), compare);//ordonare descresc dupa nivele, iar daca sunt pe acelasi nivel, dupa greutate
// afisare(a,n);
// nr cate nivele sunt folosite, si cate gutui sunt pe fiecare nivel, pentru a aloca vectori pt fiecare nivel
//
//h inaltimea maxima
int *cos;
cos = (int*)malloc(n*sizeof(int));
for(i = 0; i <n; i++)
cos[i] = 0;
int min, nec =0,poz = 0;
// int h1 = h, nr_niv = 0;
while(a[nec].inal > h && nec<n) //daca nu pot fi culese, sar peste ele ca nu ma intereseaza
nec++;
// printf("\nSunt %d gutui care un pot fi culese din start\n", nec);
int k = 0;
for(i = nec; i <n; i++)
if(a[i].inal <= h)
{
cos[k++] = a[i].greut;
for(j = i; j <n;j++)
a[j].inal+=u;
}
else
{
min = cos[0];
for(j = 1; j < k; j++)
if( cos[j] < min)
{
min = cos[j];
poz = j;
}
// printf("\nMinimul este %d, pe pozitia %d iar gutuia %d\n",min,poz,a[i].greut);
if(a[i].greut > min)
cos[poz] = a[i].greut;
// int x;
// for(x = 0; x < k ;x++)
// printf("%d ",cos[x]);
// printf("\n");
}
// printf("\n In cos am %d gutui \n",k);
int s = 0;
for(i =0; i<k; i++)
{
s += cos[i];
}
// printf("Suma maxima este: %d \n",s);
fprintf(fo, "%d",s);
free(a);
fclose(f);
fclose(fo);
return 0;
}