#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 addInVector(unsigned int *v, int N, unsigned int val)
{
int i, j, ok=0;
if(N==0)
v[0] = val;
else if(N==1)
{
if(v[0]>=val)
v[1] = val;
else
{
v[1] = v[0];
v[0] = val;
}
}
else
{
if(val > v[0])
{
for(i=N; i>=1; i--)
v[i] = v[i-1];
v[0] = val;
}
else
{
for(i=0; i<N-1; i++)
{
if( (val<=v[i]) && (val>=v[i+1]) )
{
for(j=N; j>i; j--)
v[j] = v[j-1];
v[i+1] = val;
ok=1;
break;
}
}
if(ok == 0)
v[N++] = val;
}
}
}
void removeFirst(unsigned int *v, int N)
{
int i;
for(i=1; i<N; i++)
v[i-1] = v[i];
}
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);
/*for(i=0; i<N; i++)
printf("%u %u\n", g[i].height, g[i].weight);*/
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];
//printf("Se adauga %d\n",vector[0]);
removeFirst(vector, vectorSize);
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;
//printf("Se adauga in vector %d.. => ",g[N-1].weight);
addInVector(vector, vectorSize, g[N-1].weight);
N--;
vectorSize++;
/*int j;
for(j=0; j<vectorSize; j++)
printf("%d ",vector[j]);
printf("\n");*/
}
}
printf("%d\n",Gmax);
fprintf(f2,"%u\n",Gmax);
fclose(f1);
fclose(f2);
return 0;
}