#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);
}
(*hp)[i] = w;
}
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;
}
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 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);
if(ante == in){
inserare(&hp,g[i].w,i,&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(int a, int b)
{
return a-b;
}
void merge(Gutuie **g, int p, int q)
{
int m,i,j,t=0;
Gutuie *aux;
aux = (Gutuie*)malloc((q-p+1)*sizeof(Gutuie));
m= (p + q )/ 2;
i = p;
j = m + 1;
while(i <=m && j <=q){
if(compare((*g)[i].h,(*g)[j].h) < 0 ){
aux[t] =(*g)[i];
i++;
}
else{
aux[t] = (*g)[j];
j++;
}
t ++;
}
while(i<=m){
aux[t]=(*g)[i];
i++;
t++;
}
while(j<=q){
aux[t]=(*g)[j];
j++;
t++;
}
m = p;
for(i = 0; i < t; i++){
(*g)[m] = aux[i];
m ++;
}
free(aux);
}
void MergeSort(Gutuie **g, int p, int q)
{
int m;
Gutuie gt;
if(p > q)
return;
if(q - p == 0){
return;
}
if(q - p == 1){
if(compare((*g)[p].h,(*g)[p+1].h)>0 ){
gt = (*g)[p];
(*g)[p]=(*g)[p+1];
(*g)[p+1] = gt;
return;
}
}
m = (p + q) / 2;
MergeSort(g,p,m);
MergeSort(g,m+1,q);
merge(g,p,q);
}
int main()
{ int n,H,U,nr;
FILE *f;
Gutuie *g;
read(&g,&n,&H,&U,"gutui.in");
MergeSort(&g,0,n-1);
nr = nrGutui(g,n,H,U);
f = fopen("gutui.out","w");
fprintf(f,"%d",nr);
fclose(f);
return 0;
}