//gutui
#include <stdio.h>
#include <stdlib.h>
//#include <conio.h>
int compare (const void * a, const void * b)
{
return -( *(int*)a - *(int*)b );
}
int compare2 (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
int compare1(const void * a, const void * b)
{
int **i1 = (int **)a;
int **i2 = (int **)b;
// printf("%i\n", **i1 - **i2);
return **i1 - **i2;
}
int min(int a, int b){
if(a>b) return b;
else return a;
}
int main(){
int n,h,u,i,j,niv=0,a,flag,max=-5,c=0,sum=0,k,l,z,gr;
int *sol;
int* g[2];
int* p[2];
int **m;
FILE *f;
f=fopen("gutui.in", "r");
if(!f) return -1;
fscanf(f,"%i",&n);
fscanf(f,"%i",&h);
fscanf(f,"%i",&u);
g[0]=(int*)malloc(n*sizeof(int));
g[1]=(int*)malloc(n*sizeof(int));
p[0]=(int*)malloc(n*sizeof(int));
p[1]=(int*)malloc(n*sizeof(int));
for(i=0;i<n;i++){
fscanf(f,"%i",&g[0][i]);
fscanf(f,"%i",&g[1][i]);
p[0][i]=-1;
p[1][i]=0;
}
fclose(f);
for(i=0;i<n;i++){
a=(h-g[0][i])/u + 1;
flag=0;
for(j=0;j<niv;j++){
if (a==p[0][j]) {
flag=1;
p[1][j]++;
}
else continue;
}
if (flag==0) {p[0][niv]=a; p[1][niv]=1; niv++;}
}
for(i=0;i<niv;i++){
// printf("nivel: %i nr gutui: %i\n", p[0][i],p[1][i]);
if (p[1][i]>max) max=p[1][i];
}
m=(int**)malloc(niv*sizeof(int*));
for(i=0;i<niv;i++)
m[i]=(int*)malloc((max+2)*sizeof(int));
for(i=0;i<niv;i++){
m[i][0]=p[0][i];
m[i][1]=0;
for(j=2;j<(max+2);j++){
m[i][j]=-1;
}
}
for(i=0;i<n;i++){
a=(h-g[0][i])/u + 1;
for(j=0;j<niv;j++){
if(m[j][0]==a) break;
}
a=m[j][1]+2;
m[j][a]= g[1][i];
m[j][1]++;
}
//sortez matricea m descrescator
for(i=0;i<niv;i++)
qsort (m[i]+2, m[i][1], sizeof(int), compare);
/* for(i=0;i<niv;i++){
printf("\n");
for(j=0;j<max+2;j++){
printf("%i ", m[i][j]);
}
}
printf("\n");*/
//sortez matricea m crescator , dupa prima coloana
qsort (m, niv, sizeof(int*), compare1);
//afisare matricea m
/*for(i=0;i<niv;i++){
printf("\n");
for(j=0;j<max+2;j++){
printf("%i ", m[i][j]);
}
}*/
a=m[niv-1][0]; // nivel de valoare maxima
sol=(int*)malloc(m[niv-1][0]*sizeof(int));
for(i=0;i<a;i++) sol[i]=0;
for(i=0;i<niv;i++){
if(m[i][0]-c>=m[i][1]){
for(j=2;m[i][j]!=-1 && j<max+2;j++){
sol[c]=m[i][j];
c++;
}
qsort(sol,c,sizeof(int),compare2) ;
/* printf("in if [%i]: ", m[i][0]);
for(z=0;z<a;z++) printf("%i ", sol[z]);
printf("\n"); */
}
else{
for(j=2;j<m[i][0]-c+2;j++){
sol[c]= m[i][j];
c++;
}
qsort(sol,c,sizeof(int),compare2) ;
//printf("in else [%i]: ", m[i][0]);
// for(z=0;z<a;z++) printf("%i ", sol[z]);
gr=min(m[i][0],m[i][1]);
for(k=j;k<gr+2 && m[i][k]!=-1;k++){
//verific daca vectorul de solutii partiale contine o gutuie mai usoara
// printf("k: %i ,gr: %i, ", k, gr);
for(l=0;l<c;l++){
if (sol[l]<m[i][k]) {sol[l]=m[i][k]; break;}
}
if(l==c-1) break;
}
qsort(sol,c,sizeof(int),compare2) ;
/* printf("in else [%i]: ", m[i][0]);
for(z=0;z<a;z++) printf("%i ", sol[z]);
printf("\n");*/
}
}
for(i=0;i<a;i++)
sum=sum+sol[i];
f=fopen("gutui.out","w");
fprintf(f,"%i", sum);
fclose(f);
//getch();
return 0;
}