/*
N - numar de gutui din copac
H - inaltimea maxima la care ajunge Gigel
U - cu cat se ridica crengile dupa ridicarea unei gutui
*/
#include<stdio.h>
#include<stdlib.h>
#define MAX 100000
struct pair
{
int inaltime;
int greutate;
};
void merge(struct pair *vector, int start, int middle, int end)
{
int i,j;
int n = middle - start + 1;
int m = end - middle;
struct pair *left = (struct pair *)calloc(n, sizeof(struct pair)); //parcurs cu i
struct pair *right = (struct pair *)calloc(m, sizeof(struct pair)); //parcurs cu j
//copiez elementele
for (i=0;i<n;i++)
left[i] = vector[start+i];
for (i=0;i<m;i++)
right[i] = vector[middle +1 +i];
i = 0;
j = 0;
int k = start;
while (i<n && j<m)
{
if (left[i].inaltime < right[j].inaltime)
vector[k++] = left[i++];
else
vector[k++] = right[j++];
}
while (i<n)
vector[k++] = left[i++];
while (j<m)
vector[k++] = right[j++];
free(left);
free(right);
}
void mergeSort(struct pair *vector, int start, int end)
{
int middle;
if (start < end)
{
middle = (start+end)/2;
mergeSort(vector, start, middle);
mergeSort(vector, middle+1, end);
merge(vector, start, middle, end);
}
}
//implementare heap-uri(MIN-HEAP)
int heap[MAX], dimHeap=0;
int min2(int a, int b)
{ return (a<b) ? a : b; }
int min3(int a, int b, int c)
{ return min2(min2(a,b), c); }
void swap(int *a, int i, int j)
{ int aux = a[i]; a[i]=a[j]; a[j]=aux; }
//parinte
int parinte(int i)
{ return (i-1)/2; }
//descendent stang
int DS(int i)
{ return 2*i+1; }
//descendent drept
int DD(int i)
{ return 2*i+2; }
void coboaraValoare(int *heap, int poz)
{
for (;;)
{
int valMin=heap[poz], pozitieDescendent;
if (DD(poz) <= dimHeap)
valMin = min2(valMin, heap[DD(poz)]);
if (DS(poz) <=dimHeap)
valMin = min2(valMin, heap[DS(poz)]);
if (valMin == heap[poz])
return; // Nu e nimic de facut aici
if (valMin == heap[DS(poz)])
pozitieDescendent = DS(poz);
else
pozitieDescendent = DD(poz);
swap(heap, poz, pozitieDescendent);
poz = pozitieDescendent;
}
}
void urcaValoare(int *heap ,int poz)
{
// Cat timp parintele exista si are o valoare mai mare decat nodul curent...
while (poz > 0 && heap[poz] < heap[parinte(poz)])
{
// ... interschimbam nodul curent cu parintele
swap(heap, poz, parinte(poz));
// Urcam pozitia curenta mai sus cu un nivel si reluam
poz = parinte(poz);
}
}
int minim(int *heap)
{
// Primul element din vector este cel mai mic, conform proprietatii de heap.
return heap[0];
}
int extrageMinim(int *heap)
{
// Retinem valoarea minima, o returnam la sfarsit
int min = heap[0];
// Inlocuim valoarea minima cu ultimul element din heap
swap(heap, 0, dimHeap-1);
// Scadem dimensiunea heap-ului
dimHeap--;
coboaraValoare(heap, 0);
return min;
}
void adaugaValoare(int *heap, int val)
{
// Marim dimensiunea heap-ului
dimHeap++;
// Noul element are valoarea specificata
heap[dimHeap-1] = val;
// Restabilim proprietatea de heap
urcaValoare(heap, dimHeap-1);
}
int main()
{
FILE *in = fopen("gutui.in", "r");
FILE *out = fopen("gutui.out", "w");
struct pair p[MAX];
int n, h, u, i, k=0;
int temp_h, temp_g;
fscanf(in, "%d%d%d", &n, &h, &u);
for (i=0; i<n; i++){
fscanf(in, "%d%d", &temp_h, &temp_g);
if (temp_h<=h)
{
p[k].inaltime=temp_h;
p[k].greutate=temp_g;
k++;
}
}
n = k; //!! aici raman doar la gutuile la care pot ajunge
/*
printf("\n-------------\n");
for (i=0;i<n;i++)
printf("[%d %d] ",p[i].inaltime, p[i].greutate);
*/
mergeSort(p, 0, n-1);
/*
printf("\n");
for (i=0;i <n; i++)
printf("[%d %d] ",p[i].inaltime, p[i].greutate);
printf("\n-------------\n\n");
*/
//rezolvare
int greutateMaxima=0;
int addedHeight=0;
for (i=n-1;i>=0;i--)
{
if (p[i].inaltime+addedHeight<=h)
{
adaugaValoare(heap, p[i].greutate);
greutateMaxima += p[i].greutate;
addedHeight += u; //actualizez addedHeight
}
else
{
//nu modific addedHeight
//vad daca e mai mare decat minimul gutuilor de dinainte
if (p[i].greutate > minim(heap) )
{
//atunci inseamna ca trebuie INLOCUIT cu minimul, si a
//actualizat minimul
greutateMaxima -= minim(heap);
extrageMinim(heap);
greutateMaxima += p[i].greutate;
adaugaValoare(heap, p[i].greutate);
}
}
}
//afisez la ecran
//printf("\ngreutate: %d\n", greutateMaxima);
//printf("\n");
//for (i=n-1;i>=0;i--)
//printf("%d ",enabled[i]);
fprintf(out,"%d",greutateMaxima);
//EXIT
fclose(in);
fclose(out);
return 0;
}