#include <stdio.h>
#include <malloc.h>
const char *fin="gutui.in";
const char *fout="gutui.out";
int N,H,U,GG;
int *pg, *ph;
// Functie pentru citire si validare numarului de gutui N
void readn()
{
FILE *f;
f=fopen(fin,"r");
fscanf(f,"%d %d %d",&N,&H,&U);
fclose(f);
}
// Functie pentru citirea din fisierul gutui.in a vectorilor inaltimilor si
// greutatilor
void readf(int *pg,int *ph)
{
FILE *f;
int i,j;
f=fopen(fin,"r");
fscanf(f,"%d %d %d",&N,&i,&j);
for(i=0;i<N;i++)
fscanf(f,"%d %d",ph+i,pg+i);
fclose(f);
}
// Functie pentru scrierea solutiei in fisierul gutui.out
void writef()
{
FILE *f;
f=fopen(fout,"w");
fprintf(f,"%d",GG);
fclose(f);
}
void q_sort(int numbers[],int v[], int left, int right)
{
int pivot,pivot1, l_hold, r_hold;
l_hold = left;
r_hold = right;
pivot = numbers[left];
pivot1 = v[left];
while (left < right)
{
while ((numbers[right] >= pivot) && (left < right))
right--;
if (left != right)
{
numbers[left] = numbers[right];
v[left] = v[right];
left++;
}
while ((numbers[left] <= pivot) && (left < right))
left++;
if (left != right)
{
numbers[right] = numbers[left];
v[right] = v[left];
right--;
}
}
numbers[left] = pivot;
v[left] = pivot1;
pivot = left;
pivot1 = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(numbers,v, left, pivot-1);
if (right > pivot)
q_sort(numbers,v, pivot+1, right);
}
void quickSort(int numbers[],int v[], int array_size)
{
q_sort(numbers,v, 0, array_size - 1);
}
// Initializare vector la adresa p cu 0
void init(int *p)
{
int i;
for(i=0;i<N;i++)
*(p+i)=0;
}
// Functie pentru constructia vectorului nivelelor
// gutuilor
void nivele(int *ph, int *nivel)
{
int i,j,k=1;
for(i=N-1;i>=0; i--)
{
*(nivel+i)=(H+U-*(ph+i))/U;
j=i+1;
while(j<N)
{
if(*(nivel+i)<*(nivel+j)) j++;
if(*(nivel+i)<1) break;
if(*(nivel+i)==*(nivel+j))
{
k=i;
*(nivel+i)-=1;
j=k+1;
}
else j++;
}
}
}
// Functie pentru culegere gutui
int culeg(int *p, int *vmase)
{
int i,masa;
for(masa=0,i=0;i<N;i++)
if(*(p+i)>0)
masa+=*(vmase+i);
return masa;
}
// n = numar de gutui din copac
// H = inaltimea la care poate ajunge culegatorul
// U = inaltimea cu care se ridica crengile dupa culegerea unei gutui
// vg = pointer catre vectorul maselor gutuilor
// vh = pointer catre vectorul inaltimilor la care se afla initial gutuile
// GG = masa totala a gutuilor culese
void afis(int *p, int n, char c)
{
int i;
for(i=0;i<n;i++)
printf(" %c [ %d ] = %d \n",c,i,*(p+i));
}
int main()
{
int *nivel;
readn();
ph=(int *)malloc(N*sizeof(int));
pg=(int *)malloc(N*sizeof(int));
nivel=(int *)malloc(N*sizeof(int));
readf(pg,ph);
quickSort(pg,ph,N);
init(nivel);
nivele(ph,nivel);
GG=culeg(nivel,pg);
writef();
return 0;
}