#include <stdio.h>
#include <malloc.h>
const char *fin="gutui.in";
const char *fout="gutui.out";
// N = numar de gutui din copac
// H = inaltimea la care poate ajunge culegatorul
// U = inaltimea cu care se ridica crengile dupa culegerea unei gutui
// pg = pointer catre vectorul maselor gutuilor
// ph = pointer catre vectorul inaltimilor la care se afla gutuile
// GG = masa totala a gutuilor culese
int N,H,U,GG;
int *pg, *ph;
// Functie pentru citirea datelor de intrare: N, H, U
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);
}
// Functia de sortare prin metoda quicksort
void quicksort(int pg[],int ph[], int st, int dr)
{
int aux1, aux2, salvst, salvdr;
salvst = st;
salvdr = dr;
aux1 = pg[st];
aux2 = ph[st];
while(st<dr)
{
while((pg[dr]>=aux1) && (st<dr))
dr--;
if(st != dr)
{
pg[st]=pg[dr];
ph[st]=ph[dr];
st++;
}
while((pg[st]<=aux1)&&(st<dr))
st++;
if(st != dr)
{
pg[dr]=pg[st];
ph[dr]=ph[st];
dr--;
}
}
pg[st]=aux1;
ph[st]=aux2;
aux1=st;
aux2=st;
st=salvst;
dr=salvdr;
if(st<aux1)
quicksort(pg,ph,st,aux1-1);
if(dr>aux1)
quicksort(pg,ph,aux1+1,dr);
}
// Initializare vector la adresa p cu 0
void init(int *p)
{
int i;
for(i=0;i<N;i++)
*(p+i)=0;
}
// Functie care determina prima pozitie cu indice maxim aflata inaintea
// indicelui poz cu valoare 0
int max(int v[], int n, int poz)
{
int i;
for(i=0; i<poz; i++)
if(v[poz-i-1]==0) break;
return poz-i-1;
}
// Functie pentru constructia vectorului nivelelor gutuilor
// v reprezinta vectorul pozitiilor libere la un moment dat
// (H+U-*(ph+i))/U reprezinta nivelul urmator al gutuilor
void nivele(int *ph, int *nivel)
{
int i,*v;
v=(int *)malloc(N*sizeof(int));
init(v);
for(i=N-1; i>=0; i--)
{
*(nivel+i)=(H+U-*(ph+i))/U;
if(*(nivel+i) < 1) break;
if(*(v +( *(nivel+i)-1)) ==0)
*(v + (*(nivel+i)-1))=1;
else
{
*(nivel+i)=1+ max(v,N,*(nivel+i)-1);
*(v+ (*(nivel+i)-1)) = 1;
}
}
}
// 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;
}
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, 0, N - 1);
init(nivel);
nivele(ph,nivel);
GG=culeg(nivel,pg);
writef();
return 0;
}