#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)
{
if(g[i].weight > g[j].weight) //daca 2 elemente au aceeasi inaltime, se sorteaza descrescator dupa greutate
gub[k++] = g[i++];
else
gub[k++] = g[j++];
}
else 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])
return;
else
{
interm = v[parent];
v[parent] = v[poz];
v[poz] = interm;
UrcaValoarea(v, parent);
}
}
}
void addInVector(unsigned int *v, int size, unsigned int val)
{
v[size] = val;
UrcaValoarea(v, size);
}
void removeFirst(unsigned int *v, int i, int size)
{
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];
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);
while( (HRel<=H) && (N>0 || vectorSize>0) )
{
if( vectorSize>0 )
{
Gmax += vector[0];
removeFirst(vector, 0, vectorSize);
HRel+=U;
}
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)
break;
addInVector(vector, vectorSize, g[N-1].weight);
N--;
vectorSize++;
}
}
fprintf(f2,"%u\n",Gmax);
fclose(f1);
fclose(f2);
return 0;
}