#include<stdio.h>
#include<stdlib.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 *size)
{
int i = 0;
(*hp)[*size] = w;
*size = *size + 1;
//daca dupa o inserare, numarul elementelor din heap == 1, este redundanta o refacere a heapului
if(*size == 1)
return;
i = *size -1;
while(i >0 && w > (*hp)[PARENT(i)]){
(*hp)[i] =(*hp)[PARENT(i)];
i = PARENT(i);
}
(*hp)[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 max( Heap **hp,int *size )
{
int max, i,aux,np;
if(*size == 0)
return 0;
max = (*hp)[0];
(*hp)[0] = (*hp)[(*size) -1];
aux = (*hp)[(*size) -1];
(*hp)[(*size) -1] = 0;
*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);
(*hp)[i] = (*hp)[np];
i = np;
if(CHILDONE(i) >= *size)
break;
}
(*hp)[i] = aux;
return max;
}
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);
if(ante == in){
inserare(&hp,g[i].w,&sizeh);
i++;
if (i == n){
i = m - in;
while(i > 0){
mx = max(&hp,&sizeh);
nr = nr + mx;
if(mx == 0)
break;
i --;
}
break;
}
continue;
}
nr = nr + max(&hp,&sizeh);
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);
}
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;
}
}
}
int main()
{ int n,H,U,nr;
FILE *f;
Gutuie *g;
read(&g,&n,&H,&U,"gutui.in");
qsort(g,n,sizeof(Gutuie),compare);
nr = nrGutui(g,n,H,U);
f = fopen("gutui.out","w");
fprintf(f,"%d",nr);
fclose(f);
return 0;
}