#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;
}