//#include "binheap.h"
#include <stdio.h>
#define MaxSize (1000)
//#include "binheap.h"
//#include "fatal.h"
#include <stdlib.h>
#define MinPQSize (10)
#define MinData (-32767)
//#include <stdio.h>
//#include <conio.h>
#include <string.h>
#include <stdlib.h>
typedef int ElementType;
#ifndef _BinHeap_H
#define _BinHeap_H
struct HeapStruct;
typedef struct HeapStruct *PriorityQueue;
PriorityQueue Initialize(int MaxElements);
void Destroy(PriorityQueue H);
void MakeEmpty(PriorityQueue H);
void Insert(ElementType X, PriorityQueue H);
ElementType DeleteMin(PriorityQueue H);
ElementType FindMin(PriorityQueue H);
int IsEmpty(PriorityQueue H);
int IsFull(PriorityQueue H);
#endif
struct HeapStruct {
int Capacity;
int Size;
ElementType *Elements;
};
PriorityQueue Initialize(int MaxElements) {
PriorityQueue H;
/* 1*/ if (MaxElements < MinPQSize)
/* 2*/ printf("Priority queue size is too small");
/* 3*/ H = malloc(sizeof ( struct HeapStruct));
/* 4*/ if (H == NULL)
/* 5*/ printf("Out of space!!!");
/* Allocate the array plus one extra for sentinel */
/* 6*/ H->Elements = malloc((MaxElements + 1)
* sizeof ( ElementType));
/* 7*/ if (H->Elements == NULL)
/* 8*/ printf("Out of space!!!");
/* 9*/ H->Capacity = MaxElements;
/*10*/ H->Size = 0;
/*11*/ H->Elements[ 0 ] = MinData;
/*12*/ return H;
}
/* END */
void MakeEmpty(PriorityQueue H) {
H->Size = 0;
}
/* H->Element[ 0 ] is a sentinel */
void Insert(ElementType X, PriorityQueue H) {
int i;
if (IsFull(H)) {
printf("Priority queue is full");
return;
}
for (i = ++H->Size; H->Elements[ i / 2 ] > X; i /= 2)
H->Elements[ i ] = H->Elements[ i / 2 ];
H->Elements[ i ] = X;
}
/* END */
ElementType DeleteMin(PriorityQueue H) {
int i, Child;
ElementType MinElement, LastElement;
/* 1*/ if (IsEmpty(H)) {
/* 2*/ printf("Priority queue is empty");
/* 3*/ return H->Elements[ 0 ];
}
/* 4*/ MinElement = H->Elements[ 1 ];
/* 5*/ LastElement = H->Elements[ H->Size-- ];
/* 6*/ for (i = 1; i * 2 <= H->Size; i = Child) {
/* Find smaller child */
/* 7*/ Child = i * 2;
/* 8*/ if (Child != H->Size && H->Elements[ Child + 1 ]
/* 9*/ < H->Elements[ Child ])
/*10*/ Child++;
/* Percolate one level */
/*11*/ if (LastElement > H->Elements[ Child ])
/*12*/ H->Elements[ i ] = H->Elements[ Child ];
else
/*13*/ break;
}
/*14*/ H->Elements[ i ] = LastElement;
/*15*/ return MinElement;
}
ElementType FindMin(PriorityQueue H) {
if (!IsEmpty(H))
return H->Elements[ 1 ];
printf("Priority Queue is Empty");
return H->Elements[ 0 ];
}
int IsEmpty(PriorityQueue H) {
return H->Size == 0;
}
int IsFull(PriorityQueue H) {
return H->Size == H->Capacity;
}
void Destroy(PriorityQueue H) {
free(H->Elements);
free(H);
}
#if 0
for (i = N / 2; i > 0; i--)
PercolateDown(i);
#endif
FILE* fs;
FILE* fd;
int N, max_height, height_inc,i,j,x,max_weight=0,increase=0,rest, cate_gutui, max, k, maxh;//,min,k, minmin,//kk,kkk,kkkk,maxh,r;
int aux;
/*void insert(int value, nod arb)
{
if(arb.value<value)
{
aux = arb.value;
arb.value=value;
insert_end(
}
}*/
typedef struct {
int height;
int weight;
} gutuie;
gutuie tree[100001];
int compare (const void * a, const void * b)
{
if( ( (*(gutuie*)a).height - (*(gutuie*)b).height ) == 0 )
return ( (*(gutuie*)b).weight - (*(gutuie*)a).weight );
else return ( (*(gutuie*)a).height - (*(gutuie*)b).height );
}
main() {
PriorityQueue H;
int i, j;
H = Initialize(100001);
//for (i = 0, j = MaxSize / 2; i < MaxSize; i++, j = (j + 71) % MaxSize)
//Insert(j, H);
//printf("%i", FindMin(H));
//DeleteMin(H);
//Insert(-1,H);
//printf("%i", FindMin(H));
//j = 0;
//while (!IsEmpty(H)) DeleteMin(H);
//if (DeleteMin(H) != j++)
//printf("Error in DeleteMin, %d\n", j);
//printf("Done...\n");
fs = fopen("lupu.in","r");
fd = fopen("lupu.out","w");
if (fs==NULL) {
printf("Eroare");
exit (1);
}
if (fd==NULL) {
printf("Eroare");
exit (1);
}
maxh=0;
fscanf(fs,"%i",&N);
fscanf(fs,"%i",&max_height);
fscanf(fs,"%i",&height_inc);
rest = max_height%height_inc;
max_height=max_height/height_inc;
//printf("salut");
for(i=0;i<N;i++){
fscanf(fs,"%i",&x);
if(x%height_inc>rest)
tree[i].height = x / height_inc + 1;
else
tree[i].height = x / height_inc;
fscanf(fs,"%i",&x);
tree[i].weight = x;
if(maxh<tree[i].height &&tree[i].height<=max_height) maxh=tree[i].height;
}
//increase = tree[0].height-1;
j=0;
max_weight=0;
qsort(tree,N,sizeof(gutuie),compare);
//printf("maxH %i \n", maxh);
//for(i=0;i<N;i++)
//printf("%i %i \n", tree[i].height, tree[i].weight);
for(i=tree[0].height;i<=maxh;i++)
{
while(i == tree[j].height){
Insert((0-tree[j].weight), H);
j++;
}
max_weight = max_weight - FindMin(H);
DeleteMin(H);
//printf("\n %i baubau \n", max_weight);
}
fprintf(fd,"%i",max_weight);
fclose(fs);
fclose(fd);
//getch();
return 0;
}