#include <stdlib.h>
#include <stdio.h>
typedef struct {
int h;
int g;
}gutui;
int compare(const void *a, const void *b)
{
gutui *aa = (gutui *)a;
gutui *bb = (gutui *)b;
return (bb->g -aa->g);
}
int max(gutui *a,int level,int n,int u) //inaltimea de pe levelul curent careia ii corespunde greutatea max
{
int max=0,i,j,aux=0;
for(i=0;i<n;i++)
if(a[i].h/u+1==level || a[i].h/u==level)
if(a[i].g>max)
max=a[i].g;
for(i=0;i<n;i++)
if(a[i].g==max)
aux=a[i].h;
return aux;
}
int retrieve(int test[],int index,int h_max,int u,gutui *a)
{
if(test[index]==0)
{
test[index]=1;
return 1;
}
if(test[index]==1) //daca am mai luat o gutuie de pe acest nivel
for(index;index<=h_max/u;index++)
if(test[index]==0) //daca mai pot lua gutui
{
test[index]=1;
return 1;
}
return 0;
}
int main()
{
FILE *fis=fopen("gutui.in","r");
FILE *fis_out=fopen("gutui.out","w");
int n,h_max,u,i,j,aux=0,greutate=0;
fscanf(fis,"%i",&n);
gutui a[n];
fscanf(fis,"%i",&h_max);
fscanf(fis,"%i",&u);
for(i = 0; i < n; i++)
fscanf(fis, "%i %i", &a[i].h,&a[i].g);
qsort(a,n,sizeof(gutui),compare); //gutui sortate descrescator dupa greutate
int test[h_max/u+1];
for(i=0;i<=h_max/u;i++)
test[i]=0;
for(i=0;i<n;i++)
{
if(a[i].h%u==h_max%u)
{ if(retrieve(test,a[i].h/u,h_max,u,a)==1)
greutate+=a[i].g;
}
else
if(retrieve(test,a[i].h/u+1,h_max,u,a)==1)
greutate+=a[i].g;
}
printf("Greutatea maxima este : %i",greutate);
fprintf(fis_out,"%i",greutate);
//getch();
return 0;
}