#include<stdio.h>
typedef struct element
{
int greutate;
struct nod *urm;
}nod;
void afisare(nod *x)
{
if(x==NULL)
{
printf("lista este vida \n");
return;
}
while(x!=NULL)
{
printf("greutatea: %i ",x->greutate);
x = x->urm;
}
printf("\n");
}
void inserare(nod **q,int g)
{
nod *aux,*p;
p=*q;
aux=(nod*)malloc(sizeof(nod));
aux->greutate=g;
aux->urm=NULL;
if(p==NULL)
{
*q=aux;
}
else if(p->greutate<=aux->greutate)
{
aux->urm=p;
*q=aux;
}
else
{
while(p->urm!=NULL && p->greutate>aux->greutate)
{
p=p->urm;
}
aux->urm=p->urm;
p->urm=aux;
}
}
void sterge_prim(nod **q)
{
nod *p;
p=*q;
*q=p->urm;
}
int caut_max(int N,int h[],int g[],int H,int U,int *p)
{
//printf("sunt in caut_max\n");
int i,max=0;
for(i=0;i<N;i++)
{
if((h[i]<=H+U)&&(h[i]>H)&&(g[i]>max))
{
max=g[i];
*p=i;
}
}
return max;
}
void afisare_matrice(int **a,int M,int N)
{
int i,j;
for(i=0;i<M;i++)
{
for(j=0;j<N;j++)
{
printf("%i ",a[i][j]);
}
printf("\n");
}
return 0;
}
int main()
{
int N,H,U,i,j,x,totalg=0,max,M,*h,*g,**gutui,H_curent=0,index=0;
FILE * pFile = fopen("gutui.in","r");
FILE * dFile = fopen("gutui.out","w");
fscanf(pFile,"%i",&N);
fscanf(pFile,"%i",&H);
fscanf(pFile,"%i",&U);
h=(int*)malloc(N*sizeof(int));
g=(int*)malloc(N*sizeof(int));
for(i=0;i<N;i++)
{
fscanf(pFile,"%i",&h[i]);
fscanf(pFile,"%i",&g[i]);
}
nod *prim = NULL;
M=H/U+H%U!=0; //numarul de linii in matrice
gutui=(int**)malloc(M*sizeof(int*));
{
for(i=0;i<M;i++)
{
gutui[i]=(int*)malloc(N*sizeof(int));
}
}
for(i=0;i<M;i++)
{
for(j=0;j<N;j++)
{
gutui[i][j]=0;
}
}
i=0;j=0;
//printf("H =%i",H);
while(H_curent<=H-U)
{
//printf("H_curent= %i\n",H_curent);
do
{
max=caut_max(N,h,g,H_curent,U,&x);
//printf("max dupa de cautare = %i\n",max);
gutui[i][j]=max;
if(max)
{
g[x]=0;
j++;
}
}while(max);
i++;j=0;
H_curent=H_curent+U;
}
//afisare_matrice(gutui,M,N);
prim=NULL;
for(i=0;i<M;i++)
{
if(gutui[i][0]==0 && totalg==0)
{
continue;
}
if(prim==NULL || gutui[i][0]>prim->greutate)
{
//printf("pun o gutuie de greutate: %i\n",gutui[i][0]);
totalg=totalg+gutui[i][0];
j=1;
}
else
{
//printf("pun o gutuie de greutate din coada: %i\n",prim->greutate);
totalg=totalg+prim->greutate;
sterge_prim(&prim);
j=0;
}
while(gutui[i][j]!=0)
{
//printf("i= %i j=%i \n",i,j);
inserare(&prim,gutui[i][j]);
//afisare(prim);
j++;
}
}
fprintf(dFile,"%i\n",totalg);
//printf("%i\n",totalg);
fclose(pFile);
fclose(dFile);
return 0;
}