#include <stdio.h>
#include <stdlib.h>
typedef struct copac{
int inaltime;
int greutate;
}gutui;
int compare (const void * a, const void * b){
gutui *x, *y;
x = (gutui*)a;
y = (gutui*)b;
return y->greutate - x->greutate;
}
int main(){
FILE *f = fopen("gutui.in", "r");
FILE *g = fopen("gutui.out", "w");
int N; // N = numarul de gutui din pom
fscanf(f, "%d", &N);
int H; // H = inaltimea maxima la care poate ajunge Gigel
fscanf(f, "%d", &H);
int U; // U = cu cat se ridica crengile copacului
fscanf(f, "%d", &U);
int *inaltimi, *greutati;
gutui *pom;
pom = (gutui *) malloc ( N * sizeof(gutui));
int i, j;
for (i = 0; i < N; i++){
fscanf(f, "%d", &pom[i].inaltime);
fscanf(f, "%d", &pom[i].greutate);
}
qsort(pom, N, sizeof(gutui), compare); //aici fac sortarea descrescatoare dupa greutate
//calculez momentul pentru fiecare gutuie
int *moment = (int *) malloc ( N * sizeof(int));
for ( i = 0; i < N; i++ ){
moment[i] = ( H - pom[i].inaltime) / U ;
// printf("mom: %d greutate: %d inaltime %d\n", moment[i], pom[i].greutate, pom[i].inaltime);
}
//printf("\n");
int valabil[N];
for ( i = 0; i < N; i++ ){
valabil[i] = 0;//initial toate momentele sunt accesabile
//printf("inalt: %d gre: %d mom: %d\n", pom[i].inaltime, pom[i].greutate, moment[i]);
}
//printf("\n");
int greutateaCuleasa = 0;
for ( i = 0; i < N; i++ ){
//printf("intra a %d oara in primul for\n", i);
if ( valabil[moment[i]] == 0 ){
valabil[moment[i]] = 1;
//printf("greutate: %d valabil[%d] = %d\n", pom[i].greutate, i,valabil[moment[i]] );
//printf("in if adaug greutatea: %d de la %d cu momentul: %d\n", pom[i].greutate, pom[i].inaltime, moment[i]);
greutateaCuleasa += pom[i].greutate;
}
else{
//printf("intra in else\n");
//printf(" greutate: %d valabil[%d] = %d\n", pom[i].greutate, i,valabil[moment[i]] );
for ( j = moment[i]; j >= 0; j-- ){
//printf("moment[%d] = %d\n", j, moment[j]);
if ( valabil[j] == 0 ){
valabil[moment[j]] = 1;
//printf("in else adaug greutatea: %d de la %d cu momentul: %d\n", pom[i].greutate, pom[i].inaltime, moment[i]);
greutateaCuleasa += pom[i].greutate;
break;
}
}
}
}
/* i = 0;
while ( pom[i].inaltime + i * U < H && i < N ){
printf("inaltime = %d greutate: %d\n", pom[i].inaltime, pom[i]. greutate);
for ( int j = i; j < N; j++ ){
if ( pom[j].inaltime + i * U < H ){
greutateaCuleasa += pom[i].greutate;
printf("greutateaCuleasa: %d inaltime: %d greutate: %d\n", greutateaCuleasa, pom[j].inaltime, pom[j].greutate);
i = j;
break;
//i = j;
}
}
i++;
}*/
// printf("\n");
// printf("greutatea finala: %d\n", greutateaCuleasa);
// printf("\n");
// printf("%d %d %d\n", N, H, U);
//for ( i = 0; i < N; i++ )
//printf("%d %d\n", pom[i].inaltime, pom[i].greutate);
fprintf(g, "%d", greutateaCuleasa);
fclose(f);
fclose(g);
//getchar();
return 0;
}