#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;
} 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;
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 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*));
for(i=0;i<k;i++)
zona[i]=CV(1);
for (i=0;i<n;i++)
if (fr[i].h<=h){
niv=k-1-(h-fr[i].h)/u;
AdaugaValoare(zona[niv],fr[i].g);
}
while (1){
max=-1;
poz=-1;
for (i=0;i<j;i++)
if(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;
}
for (i=0;i<k;i++)
ElibereazaVector(zona[i]);
fprintf(g,"%d\n",s);
fclose(f);
fclose(g);
return 0;
}