#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);
}
/*
int poz(int k,int p)
{
int x,i,j;
x=*(pg+k);
i=k;
j=p;
while(i<j)
{
while(*(pg+j)<x) // Tip sortare descrescatoare
j--;
while(*(pg+i)>x) // Tip sortare descrescatoare
i++;
if(i<j)
{
x=*(pg+i);*(pg+i)=*(pg+j);*(pg+j)=x;
x=*(ph+i);*(ph+i)=*(ph+j);*(ph+j)=x;
}
else return j;
}
}
void quick(int k, int p)
{
int s;
if(k<p)
{
s=poz(k,p);
quick(k,s);
quick(s+1,p);
}
}
*/
/*// Sortare descrescatoare
void sortd(int *ph, int *pg)
{
int i,j,aux;
for(i=0;i<N;i++)
for(j=i+1;j<N;j++)
if(*(pg+i)<*(pg+j))
{
aux=*(pg+i);
*(pg+i)=*(pg+j);
*(pg+j)=aux;
aux=*(ph+i);
*(ph+i)=*(ph+j);
*(ph+j)=aux;
}
}
*/
void shell_sort(int *pg , int *ph, int n){
int salt[8]={701,301,132,57,23,10,4,1};//aceasta este cea mai buna secventa pentru vectorul de salturi
int nit=8;
int i,j,aux1,aux2,k;
for(k=nit-1; k>=0; k--)
{
for(i=salt[k];i<=n-1; i++)
{
aux1=*(pg+i);//2
aux2=*(ph+i);
j=i-salt[k];//3
while((j>=0)&&(*(pg+j)<aux1))
{
//v[j+salt[k]]=v[j];
*(pg+j+salt[k])=*(pg+j);
*(ph+j+salt[k])=*(ph+j);
j=j-salt[k];
}
//v[j+salt[k]]=aux;
*(pg+j+salt[k])=aux1;
*(ph+j+salt[k])=aux2;
}
}
}
// 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;
for(i=0;i<N;i++)
*(nivel+i)=(H+U-*(ph+i))/U;
//*(nivel+i)=(H-*(ph+i))/10+1;
for(i=0;i<N;i++)
{
j=0;
while(j<i)
{
if(*(nivel+i)==*(nivel+j))
{
*(nivel+i)-=1;
j=0;
}
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 N=4,H=100,U=10;
//int hg[4]={91,82,93,94}, mg[4]={10,30,5,15};
//int N=6,H=100,U=10;
//int hg[6]={71,72,73,82,91,92}, mg[6]={20,30,30,5,15,25};
//int N=9,H=100,U=10;
//int hg[9]={40,20,70,80,50,30,60,30,50}, mg[9]={2,1,1,3,1,2,3,2,2};
int *nivel;
readn();
ph=(int *)malloc(N*sizeof(int));
pg=(int *)malloc(N*sizeof(int));
nivel=(int *)malloc(N*sizeof(int));
readf(pg,ph);
//printf(" Vector greutati nesortat \n");
//system("pause");
//afis(pg,N,'G');
//printf("\n\n");
//printf(" Vector inaltimi nesortat \n");
//system("pause");
//afis(ph,N,'H');
//system("pause");
//printf("\n\n");
//quick(0,N-1);
shell_sort(pg,ph,N);
//printf(" Vectori sortati \n");
//afis(pg,N,'G');
//printf("\n\n");
//afis(ph,N,'H');
//printf("\n\n");
//sortd(ph,pg);
init(nivel);
nivele(ph,nivel);
//afis(nivel,N,'N');
GG=culeg(nivel,pg);
//printf(" Masa totala este %d \n",GG);
//system("pause");
writef();
return 0;
}