#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
/* Structura heap_vector_struct retine heap-ul avand drept camp un vector de intregi , si alte doua campuri
* reprezentand capacitatea , repsectiv dimensiunea heap-ului .
*/
typedef struct heap_vector_struct
{
int *values;
int dimVect;
int capVect;
int niv;
} HeapVector;
typedef struct gutui{
int h;
int g;
} gutui;
int DescS(HeapVector *h, int poz)
{
if ((2*poz+1)>=h->dimVect)
return -1;
else
return (2*poz+1);
}
int DescD(HeapVector *h, int poz)
{
if ((2*poz+2)>=h->dimVect)
return -1;
else
return (2*poz+2);
}
int Parinte(HeapVector *h, int poz)
{
if (poz==0)
return -1;
else
return (poz-1)/2;
}
HeapVector* CV(int capVect)
{
HeapVector *h;
h=(HeapVector*)malloc(sizeof(HeapVector));
h->values=(int*)calloc(capVect,sizeof(int));
h->dimVect=0;
h->capVect=capVect;
h->niv=-1;
return h;
}
void ElibereazaVector(HeapVector *h)
{
free(h->values);
free(h);
}
void CoboaraValoare(HeapVector *h, int poz)
{
int pozdesc=0;
int valmax,aux;
for (;;)
{
valmax=h->values[poz];
if (DescS(h,poz)!=-1)
if (h->values[DescS(h,poz)]>valmax)
valmax=h->values[DescS(h,poz)];
if (DescD(h,poz)!=-1)
if (h->values[DescD(h,poz)]>valmax)
valmax=h->values[DescD(h,poz)];
if (valmax==h->values[poz])
return;
if (DescS(h,poz)!=-1&&valmax==h->values[DescS(h,poz)])
pozdesc=DescS(h,poz);
else
if (DescD(h,poz)!=-1)
pozdesc=DescD(h,poz);
aux=h->values[pozdesc];
h->values[pozdesc]=h->values[poz];
h->values[poz]=aux;
poz=pozdesc;
}
}
void UrcaValoare(HeapVector *h,int poz) {
int aux;
while (poz>0&&h->values[poz]>h->values[Parinte(h,poz)])
{
aux=h->values[Parinte(h,poz)];
h->values[Parinte(h,poz)]=h->values[poz];
h->values[poz]=aux;
poz=Parinte(h,poz);
}
}
int Maxim(HeapVector *h){
assert(h->dimVect>0) ;
return h->values[0];
}
int ExtrageMaxim(HeapVector *h){
assert(h->dimVect>0);
int min,aux;
min=h->values[0];
aux=h->values[0];
h->values[0]=h->values[h->dimVect-1];
h->values[h->dimVect-1]=aux;
h->dimVect--;
CoboaraValoare(h,0);
return min;
}
void AdaugaValoare(HeapVector *h,int val){
if (h->dimVect==h->capVect){
h->capVect=2*h->capVect;
h->values=(int*)realloc(h->values,h->capVect*sizeof(int));
}
h->dimVect++;
h->values[h->dimVect-1] = val;
UrcaValoare(h,h->dimVect-1);
}
int size(HeapVector *h){
return h->dimVect;
}
int partitie(gutui x[],int s,int d){
int piv=x[s].h;
int j=d+1,i=s-1;
gutui aux;
while(1){
do{j--;} while(x[j].h>piv);
do{i++;} while(x[i].h<piv);
if (i<j){
aux=x[i];
x[i]=x[j];
x[j]=aux;
}
else return j;
}
}
void quicksort(gutui x[],int s,int d){
if(s<d){
int p=partitie(x,s,d);
quicksort(x,s,p);
quicksort(x,p+1,d);
}
}
int main(){
FILE *f=fopen("gutui.in","r");
FILE *g=fopen("gutui.out","w");
int u,h,n,i,j=1,max,poz,s=0;
gutui *fr;
HeapVector** zona;
fscanf(f,"%d%d%d",&n,&h,&u);
fr=(gutui*)malloc(n*sizeof(gutui));
for (i=0;i<n;i++)
fscanf(f,"%d%d",&fr[i].h,&fr[i].g);
int k=h/u+1,niv;
zona=(HeapVector**)calloc(k,sizeof(HeapVector*));
int nr=-1,r=-1;
quicksort(fr,0,n-1);
//for (i=0;i<n;i++)
// printf("%d %d\n",fr[i].h,fr[i].g);
for (i=0;i<n;i++){
niv=k-1-(h-fr[i].h)/u;
if(r==niv)
AdaugaValoare(zona[nr],fr[i].g);
else{
nr++;
zona[nr]=CV(1);
AdaugaValoare(zona[nr],fr[i].g);
zona[nr]->niv=niv;
r=niv;
}
}
nr++;
/*for (i=0;i<nr;i++){
printf("%d : ",zona[i]->niv);
for (j=0;j<size(zona[i]);j++)
printf("%d ",zona[i]->values[j]);
printf("\n");
}*/
j=1;
while (1){
max=-1;
poz=-1;
for (i=0;i<nr;i++)
if(zona[i]->niv<j&&size(zona[i])!=0&&Maxim(zona[i])>max){
max=Maxim(zona[i]);
poz=i;
}
if (poz!=-1){
s+=max;
ExtrageMaxim(zona[poz]);
}
j++;
if (j==k+1) break;
//if (p==nr) break;
//printf("%d\n",zona[p]->niv);
//if (j==zona[p]->niv) p++;
//printf("%d ",zona[p]->niv);
}
//for (i=0;i<k;i++)
// ElibereazaVector(zona[i]);
fprintf(g,"%d\n",s);
fclose(f);
fclose(g);
return 0;
}