#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MAX(a,b)( (a-b <=0) ? ( b):(a) )
#define PARENT(i) ((i % 2 == 0 )?(i/2 -1) : (i/2))
#define CHILDONE(i) (2*i + 1)
#define CHILDTWO(i) (2*i + 2)
typedef int Heap;
typedef struct gut{
int h,w;
}Gutuie;
void inserare(Heap **hp, int w, int in, int *size)
{ int i = 0;
(*hp)[*size] = w;
*size = *size + 1;
if(*size == 1)
return;
i = *size -1;
while(i >0 && w > (*hp)[PARENT(i)]){
(*hp)[i] =(*hp)[PARENT(i)];
i = PARENT(i);
}
//printf("i %d este di w este %d\n",i,w);
(*hp)[i] = w;
}
int max( Heap **hp,int *size )
{
int max, i,aux,np;
if(*size == 0)
return 0;
max = (*hp)[0];
//printf("size %d \n",*size);
// printf("inainte\n");
// for(i = 0; i< *size; i++)
// printf("%d ", (*hp)[i]);
// printf("\n");
(*hp)[0] = (*hp)[(*size) -1];
aux = (*hp)[(*size) -1];
(*hp)[(*size) -1] = 0;
// printf("au este %d \n",aux);
*size = *size - 1;
if(*size == 1)
return max;
i = 0;
while(i < *size && ((*hp)[CHILDONE(i)] > aux || (*hp)[CHILDTWO(i)] > aux) ){
np = MAX( (*hp)[CHILDONE(i)],(*hp)[CHILDTWO(i)]);
if (np == (*hp)[CHILDONE(i)])
np = CHILDONE(i);
else
np = CHILDTWO(i);
//printf("np este %d ",np);
(*hp)[i] = (*hp)[np];
i = np;
if(CHILDONE(i) >= *size)
break;
}
// printf("i este %d si aux este %d \n",i,aux);
(*hp)[i] = aux;
// printf("dupa\n");
// for(i = 0; i< *size; i++)
// printf("%d ", (*hp)[i]);
// printf("\n");
return max;
}
void read(Gutuie **g, int *n, int *H, int *U, char *file)
{
FILE *f;
int i = 0,hh,gg;
f = fopen(file, "r");
fscanf(f,"%d %d %d ",n,H,U);
(*g) = (Gutuie *)malloc((*n)*sizeof(Gutuie));
*n = 0;
while(fscanf(f,"%d %d ",&hh,&gg) > 0 ){
if(hh <= *H){
(*g)[i].h = hh;
(*g)[i].w = gg;
i++;
(*n) = (*n) + 1;
}
}
/*
for(i = 0; i < *n;i++){
printf("gutuia %d are h de %d i cantareste %d \n",i,(*g)[i].h,(*g)[i].w);
}
*/
}
int interval(int U, int H, int n){
int r;
r = H % U;
if(n <= r)
return 0;
if(r == 0){
if(n % U == 0)
return (n/U -1);
else
return n/U;
}
n = n - r;
if(n % U == 0)
return n/U;
else
return n/U + 1;
}
int nrGutui(Gutuie *g, int n, int H, int U)
{
int i,m,nr = 0,ante,in,sizeh,mx;
Heap *hp;
hp = (Heap*)malloc(n * sizeof(Heap));
if(H % U == 0)
m = H / U ;
else
m = H / U + 1;
i = 0;
ante = interval(U,H,g[0].h);
sizeh = 0;
while(i < n){
in = interval(U,H,g[i].h);
// printf("intervalul la h %d este %d si ante este %d\n ",g[i].h,in,ante);
if(ante == in){
inserare(&hp,g[i].w,i,&sizeh);
i++;
if (i == n){
i = m - in;
//printf("m este %d \n",m);
while(i > 0){
mx = max(&hp,&sizeh);
// printf("ultim mx este %d si i este %d intervalul este %d\n",mx,i,in);
nr = nr +mx;
if(mx == 0)
break;
i --;
}
break;
}
continue;
}
mx = max(&hp,&sizeh);
// printf("max este %d si i este %d intervalul este %d\n",mx,i,in);
nr = nr + mx;
ante ++;
}
return nr;
}
int compare(const void *a, const void *b)
{
Gutuie *m,*n;
m = (Gutuie*)a;
n = (Gutuie*)b;
return (m->h - n->h);
}
int main()
{ int n,H,U,nr;
FILE *f;
Gutuie *g;
read(&g,&n,&H,&U,"gutui.in");
qsort(g,n,sizeof(Gutuie),compare);
// for(i = 0 ; i< n; i++)
// printf(" gutuia %d are h %d si w %d\n",i,g[i].h,g[i].w);
nr = nrGutui(g,n,H,U);
f = fopen("gutui.out","w");
fprintf(f,"%d",nr);
fclose(f);
return 0;
}