#include <stdio.h>
#define MAX_NUM 100000
typedef struct{
unsigned int height; //inaltimea la care se afla gutuia
unsigned int weight; //greutatea gutuii
char isInTree; //0 daca nu e in copac, 1 altfel
} 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 greutate, se sorteaza descrescator dupa inaltime
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 greutate
{
if(p == q)
return;
int m = (p+q)/2;
MergeSort(g, p, m);
MergeSort(g, m+1, q);
Merge(g, p, q);
}
int CanTakeFromTree(Gubbins *g, int N, unsigned int HRel, unsigned int H)
{ //functie care intoarce primul indice al gutuii care se poate lua din copac
int j;
for(j=0; j<N; j++)
if(g[j].isInTree == 1)
if( (g[j].height+HRel) <= H)
return j;
return -1;
}
int main()
{
FILE *f1 = fopen("gutui.in","r"), *f2 = fopen("gutui.out","w");
int N, i, j;
unsigned int H, U, Gmax = 0, HRel = 0;
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);
g[i].isInTree = 1;
}
/*for(i=0; i<N; i++)
printf("%u %u %d\n", g[i].height, g[i].weight, g[i].isInTree);*/
MergeSort(g, 0, N-1);
/*printf("\n");
for(i=0; i<N; i++)
printf("%u %u\n", g[i].height, g[i].weight);
*/
while( (j = CanTakeFromTree(g, N, HRel, H)) >= 0 )
{
Gmax = Gmax + g[j].weight;
g[j].isInTree = 0;
HRel += U;
}
/*printf("%u\n",Gmax);*/
fprintf(f2,"%u\n",Gmax);
fclose(f1);
fclose(f2);
return 0;
}