#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;
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;
int valmin,aux;
for (;;)
{
valmin=h->values[poz];
if (DescS(h,poz)!=-1)
if (h->values[DescS(h,poz)]>valmin)
valmin=h->values[DescS(h,poz)];
if (DescD(h,poz)!=-1)
if (h->values[DescD(h,poz)]>valmin)
valmin=h->values[DescD(h,poz)];
if (valmin==h->values[poz])
return;
if (DescS(h,poz)!=-1&&valmin==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 Parinte(HeapVector *h, int poz)
{
if (poz==0)
return -1;
else
return (poz-1)/2;
}
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 Minim(HeapVector *h)
{
assert(h->dimVect>0) ;
return h->values[0];
}
int ExtrageMinim(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)
{
h->dimVect++;
h->values[h->dimVect-1] = val;
UrcaValoare(h,h->dimVect-1);
}
int size(HeapVector *h)
{
return h->dimVect;
}
typedef struct gutui{
int h;
int g;
} gutui;
typedef struct node {
gutui fr;
struct node* next;
} node;
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;
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);
//quicksort(fr,0,n-1);
node *p,*q;
int k=h/u+1,niv;
zona=(HeapVector**)calloc(k,sizeof(HeapVector*));
for(i=0;i<k;i++)
zona[i]=CV(n);
for (i=0;i<n;i++)
if (fr[i].h<=h){
niv=k-1-(h-fr[i].h)/u;
//if (zona[niv]==0)
// zona[niv]=CV(n);
AdaugaValoare(zona[niv],fr[i].g);
}
int j=1,max,poz,s=0;
/*
for (i=0;i<k;i++){
if (size(zona[i])==0) printf("gol");
else
for (j=0;j<zona[i]->dimVect;j++)
printf("%d ",zona[i]->values[j]);
printf("\n");
}
*/
j=1;
while (1){
max=-1;
poz=-1;
for (i=0;i<j;i++)
if(size(zona[i])!=0&&Minim(zona[i])>max){
max=Minim(zona[i]);
poz=i;
}
if (poz!=-1){
//printf("Am ales %d %d\n",zona[poz]->fr.h,zona[poz]->fr.g);
s+=max;
ExtrageMinim(zona[poz]);
}
j++;
if (j==k+1) break;
}
fprintf(g,"%d\n",s);
fclose(f);
fclose(g);
return 0;
}