/*Paraschiv Ionut Cristian - 324CA*/
#include <stdio.h>
#define MAX_NUM 100000
typedef struct{
unsigned int height; //inaltimea la care se afla gutuia
unsigned int weight; //greutatea gutuii
} Gubbins;
void Merge(Gubbins *g, int p, int q)
{
int len = q-p+1;
Gubbins gub[len];
int m = (p+q)/2;
int i=p, j=m+1, k=0;
while(i<=m && j<=q)
{
if(g[i].height <= g[j].height)
gub[k++] = g[j++];
else
gub[k++] = g[i++];
}
while(i<=m)
gub[k++] = g[i++];
while(j<=q)
gub[k++] = g[j++];
for(i=0; i<len; i++)
g[p+i] = gub[i];
}
void MergeSort(Gubbins *g, int p, int q) //sortare descrescatoare dupa inaltime
{
if(p == q)
return;
int m = (p+q)/2;
MergeSort(g, p, m);
MergeSort(g, m+1, q);
Merge(g, p, q);
}
void UrcaValoarea(unsigned int *v, int poz)
{
int parent=(poz-1)/2;
unsigned int interm;
if(parent>=0)
{
if(v[parent]>=v[poz]) //se urca valoarea pana se indeplineste aceasta relatie (specifica heapului maximal)
return;
else
{
interm = v[parent]; //daca nu se respecta relatia se interschimba cu parintele si se trece mai departe
v[parent] = v[poz];
v[poz] = interm;
UrcaValoarea(v, parent);
}
}
}
void addInVector(unsigned int *v, int size, unsigned int val) //adaugare in Heap
{
v[size] = val; //se adauga pe ultima pozitie, si se urca valoarea
UrcaValoarea(v, size);
}
void removeFirst(unsigned int *v, int i, int size) //se sterge din heap primul element (maximul)
{ //acesta se muta la sfarsitul heapului si se seteaza ca fiind 0
int l = (2*i+1), r = (2*i+2);
if( l>=size && r>=size )
{
v[i] = 0; //frunza
return;
}
else if (l<size && r>=size)
{
v[i] = v[l];
removeFirst(v, l, size);
}
else if (l>=size && r<size)
{
v[i] = v[r];
removeFirst(v, r, size);
}
else if(l<size && r<size)
{
if(v[l]>v[r])
{
v[i] = v[l];
removeFirst(v, l, size);
}
else
{
v[i] = v[r];
removeFirst(v, r, size);
}
}
}
int main()
{
FILE *f1 = fopen("gutui.in","r"), *f2 = fopen("gutui.out","w");
int N, i, vectorSize = 0, first_iter=1;
unsigned int H, U, Gmax = 0, HRel, vector[MAX_NUM];
Gubbins g[MAX_NUM]; //vectorul de structuri in care se retin H+G ale gutuilor
fscanf(f1, "%d %u %u\n", &N, &H, &U);
for(i=0; i<N; i++)
fscanf(f1, "%u %u\n",&g[i].height, &g[i].weight);
MergeSort(g, 0, N-1);
if(H%U == 0)
HRel = U; //pozitia relativa pe ultimul nivel
else
HRel = H - ((H/U)*U); //pozitia relative in cazul in care H nu se divide la U
while( (HRel<=H) && (N>0 || vectorSize>0) )
{
if( vectorSize>0 ) //daca exista elemente in heap, se scoate maximul (primul element)
{
Gmax += vector[0];
removeFirst(vector, 0, vectorSize);
HRel+=U; //se incrementeaza inaltimea relativa
}
else if(first_iter == 0)
HRel+=U; //nu se adauga U la prima iteratie
first_iter = 0;
while(N>0)
{
if(g[N-1].height > HRel) //cat timp inaltimile se incadreaza in intervalul inaltimii relative,
break; //se adauga in heap gutui
addInVector(vector, vectorSize, g[N-1].weight);
N--;
vectorSize++;
}
}
fprintf(f2,"%u\n",Gmax);
fclose(f1);
fclose(f2);
return 0;
}