//Tigora Andrei 322CA
#include<stdio.h>
#include<stdlib.h>
typedef struct {
unsigned int w;
unsigned int h;
} gutuie;
typedef struct {
int max;
int crt;
unsigned int* w;
} heap;
int compare(gutuie a,gutuie b){
if(a.h<b.h)
return -1;
if(a.h>b.h)
return 1;
if(a.w>b.w)
return -1;
if(a.w<b.w)
return 1;
return 0;
}
void merge_sort(gutuie *vect,int size){
gutuie aux;
if(size==1)
return;
if(size==2){
if(compare(vect[0],vect[1])>0){
aux = vect[0];
vect[0] = vect[1];
vect[1] = aux;
}
return;
}
int middle = size/2,i,j,crt;
gutuie *vect1 = malloc((middle)*sizeof(gutuie));
gutuie *vect2 = malloc((size-middle)*sizeof(gutuie));
for(i=0;i<middle;i++)
vect1[i] = vect[i];
for(i=middle;i<size;i++)
vect2[i-middle] = vect[i];
merge_sort(vect1,middle);
merge_sort(vect2,size-middle);
i = 0, j = 0, crt = 0;
while(i<middle && j<size-middle)
if(compare(vect1[i],vect2[j])<=0)
vect[crt++] = vect1[i++];
else
vect[crt++] = vect2[j++];
while(i<middle)
vect[crt++] = vect1[i++];
while(j<size-middle)
vect[crt++] = vect2[j++];
free(vect1);free(vect2);
}
void remove_first(heap *choice){
choice->crt--;
choice->w[0] = choice->w[choice->crt];
int poz = 0;
unsigned int aux;
while(1){
if(poz*2+2<choice->crt){ //are ambii fii
if(choice->w[poz*2+1]<choice->w[poz]){
if(choice->w[poz*2+2]<choice->w[poz*2+1]){
aux = choice->w[poz];
choice->w[poz] = choice->w[poz*2+2];
choice->w[poz*2+2] = aux;
poz = poz*2+2;
}
else{
aux = choice->w[poz];
choice->w[poz] = choice->w[poz*2+1];
choice->w[poz*2+1] = aux;
poz = poz*2+1;
}
}
else{
if(choice->w[poz*2+2]<choice->w[poz]){
aux = choice->w[poz];
choice->w[poz] = choice->w[poz*2+2];
choice->w[poz*2+2] = aux;
poz = poz*2+2;
}
else
break;
}
}
else
if(poz*2+2<choice->crt){
if(choice->w[poz*2+1]<choice->w[poz]){
aux = choice->w[poz];
choice->w[poz] = choice->w[poz*2+1];
choice->w[poz*2+1] = aux;
poz = poz*2+1;
}
else
break;
}
else
break;
}
}
void add(heap *choice,unsigned int val){
int poz = choice->crt;
unsigned int aux;
choice->crt++;
choice->w[poz] = val;
while(poz)
if(choice->w[poz]<choice->w[(poz-1)/2]){
aux = choice->w[poz];
choice->w[poz] = choice->w[(poz-1)/2];
choice->w[(poz-1)/2] = aux;
poz = (poz-1)/2;
}
else
break;
}
int main(){
int i,crt,n;
gutuie *vect;
int high_max,low;
long suma = 0;
heap choice;
FILE *in,*out;
in = fopen("gutui.in","r");
out = fopen("gutui.out","w");
//fprintf(stdout,"Long live eu!\n");
fscanf(in,"%d%d%d",&n,&high_max,&low);
//fprintf(stdout,"\n%d %d %d\n",n,high_max,low);
vect = malloc(n*sizeof(gutuie));
crt = 0;
for(i=0;i<n;i++){
fscanf(in,"%d%d",&vect[i].h,&vect[i].w);
if(vect[crt].h<=high_max){ // gutuie accesibila
crt++;
//fprintf(stdout,"gutuie acceptata\n");
}
}
if(crt==0){
fprintf(out,"0");
return 0;
}
n = crt;
// Inaltimea este inlocuita cu nivelul corespunzator
for(i=0;i<n;i++){
// fprintf(stdout,"%d %d %d\n",high_max,vect[i].h,vect[i].w);
vect[i].h = ((high_max - vect[i].h) / low) + 1;
//fprintf(stdout,"%d %d\n\n",vect[i].h,vect[i].w);
}
// Sorteaza corespunzator
// printf("Imediat dupa merge\n");
merge_sort(vect,n);
//for(i=0;i<n;i++)
// fprintf(stdin,"%d %d\n",vect[i].h,vect[i].w);
// Initializeaza minheapul
if(vect[n-1].h > n){
choice.w = malloc(n*sizeof(unsigned int));
choice.max = n;
}
else{
choice.w = malloc(vect[n-1].h*sizeof(unsigned int));
choice.max = vect[n-1].h;
}
choice.crt=0;
// Adauga in minheap
//fprintf(stdout,"La minheap\n");
for(i=0;i<n;i++){
//fprintf(stdout,"%d %d\n",vect[i].h,vect[i].w);
if(vect[i].h>choice.crt)//mai sunt gutui accesibile pe nivelul curent
add(&choice,vect[i].w);
else if(vect[i].w > choice.w[0]){//gutuia curenta reprezinta o alegerea mai buna decat cea mai slaba alegere anterioara
//printf("Nu merge inlocuit\n");
remove_first(&choice);
add(&choice,vect[i].w);
}
//printf("heapul are crt = %d, minumul = %d\n",choice.crt,choice.w[0]);
}
//fprintf(stdout,"\n%d %d %d\n\t heapul are %d pozitii\n",n,high_max,low,choice.max);
/*
for(i=0;i<choice.max;i++)
fprintf(stdout,"%d ",choice.w[i]);
fprintf(stdout,"\n");
*/
/*
for(i=0;i<choice.max;i++)
suma+=choice.w[i];
*/
while(choice.crt){
//fprintf(stdout,"%d ",choice.w[0]);
suma+=choice.w[0];
remove_first(&choice);
}
fprintf(out,"%ld",suma);
fclose(in);fclose(out);
// End
return 0;
}