#include <stdio.h>
#include <stdlib.h>
typedef struct
{
unsigned int niv,kg;
}GUTUIE;
int comp(const void *a,const void *b) //functia de comparare, sorteaza descrescator dupa inaltime
{ //daca doua gutui au aceeasi inaltime, sunt sortate descrescator dupa greutate
unsigned int h1=((GUTUIE*)a)->niv;
unsigned int h2=((GUTUIE*)b)->niv;
if(h1==h2)
{
unsigned int kg1=((GUTUIE*)a)->kg;
unsigned int kg2=((GUTUIE*)a)->kg;
return kg2-kg1;
}
return h2-h1;
}
void updateIns(unsigned int heap[],int index) //functia de actualizare a heap-ului dupa inserarea unui element
{
int root=(index-1)/2;
if(heap[root]>heap[index])
{
unsigned int aux;
aux=heap[root];
heap[root]=heap[index];
heap[index]=aux;
updateIns(heap,root);
}
}
void hIns(unsigned int heap[],unsigned int *dim,int val) //inserare la capatul heap-ului, si actualizarea sa
{
heap[(*dim)]=val;
updateIns(heap,(*dim));
(*dim)++;
}
void updateRem(unsigned int heap[],unsigned int dim,int root) //functia de actualizare a heap-ului dupa stergerea unui element
{
unsigned int lNode=root*2+1,rNode=root*2+2,minNode=root;
if(lNode<dim&&heap[lNode]<heap[minNode])
minNode=lNode;
if(lNode<dim&&heap[rNode]<heap[minNode])
minNode=rNode;
if(minNode!=root)
{
unsigned int aux=heap[minNode];
heap[minNode]=heap[root];
heap[root]=aux;
updateRem(heap,dim,minNode);
}
}
void hRem(unsigned int heap[],unsigned int *dim) //stergere din varful heap-ului si actualizarea sa
{
(*dim)--;
heap[0]=heap[(*dim)];
updateRem(heap,*dim,0);
}
int main()
{
freopen("gutui.in","r",stdin);
freopen("gutui.out","w",stdout);
unsigned int i,dim=0,sol=0,N,N2=0,H,U,niv,kg,heap[100000];
GUTUIE vgutui[100000];
scanf("%d %d %d",&N,&H,&U);
//H/=U;
for(i=0;i<N;i++)
{
scanf("%d %d",&niv,&kg);
if(niv<=H) {vgutui[N2].niv=niv;vgutui[N2].kg=kg;N2++;}//daca gutuia citita este la o inaltime
//mai mare decat H, nu mai este introdusa in vector
}
N=N2;
qsort(vgutui,N,sizeof(GUTUIE),comp); //sortare vector gutui
hIns(heap,&dim,vgutui[0].kg); //inserarea primului element din vector in radacina heap-ului
H-=U;
for(i=1;(i<N)&&(H>=0);i++)
if(vgutui[i].niv>H) //daca gutuia curenta este la o inaltime mai mare decat inaltimea maxima curenta
{ //si daca greutatea acesteia este mai mare decat ce este in radacina heap-ului,
if(vgutui[i].kg>heap[0]) //se sterge ce este in radacina heap-ului si se introduce greutatea gutuii curente
{
hRem(heap,&dim);
hIns(heap,&dim,vgutui[i].kg);
}
}
else //altfel se introduce greutatea gutuii curente, si se scade inaltimea maxima cu U
{
hIns(heap,&dim,vgutui[i].kg);
H-=U;
//H--;
}
for(i=0;i<dim;i++) //rezultatul va fi suma elementelor din heap
sol+=heap[i];
printf("%d",sol);
return 0;
}