#include <stdio.h>
#include <stdlib.h>
void printVec (int *vec, int n)
{
int i;
for (i = 0; i < n; i++)
{
printf("%2d ", vec[i]);
}
printf("\n");
}
void swap (int *vec, int n, int poz)
{
int aux;
aux = vec[n - 1];
vec[n - 1] = vec[poz];
vec[poz] = aux;
}
// TODO si in dependenta de inaltime;
int findMax (int *wheigh, int *high, int n, int down, int up)
{
int i;
int max = 0;
int poz = -1;
for (i = 0; i < n; i++)
{
// printf("%d %d\n", high[i], low);
if (high[i] > down && high[i] <= up)
{
if (wheigh[i] > max)
{
max = wheigh[i];
poz = i;
}
if (wheigh[i] == max)
{
if (high[i] > high[poz])
{
poz = i;
}
}
}
}
return poz;
}
int functionX (int *high, int *wheigh, int *n, int poz, int *h, int u, int *gmax)
{
int i, temp;
int nr = 0;
int index, up;
temp = (*h);
up = (*h);
while (temp > high[poz])
{
temp = temp - u;
nr++;
}
// printf("NR == %d\n", nr);
// (*h) = (*h) - (u * nr);// !!
// printVec (wheigh, (*n));
// printf("Culeg gutuia cu greutate maxima %d %d\n", high[poz], wheigh[poz]);
(*gmax) += wheigh[poz];
swap (high, (*n), poz);
swap (wheigh, (*n), poz);
(*n)--;
nr--;
(*h) -= u;
// printVec (high, (*n));
// printVec (wheigh, (*n));
while (nr > 0)
{
index = findMax (wheigh, high, (*n), temp, up);
if (index == -1)
{
break;
}
// printf("GMAX == %d INDEX == %d\n", (*gmax), index);
// printf("Culeg %d %d\n", high[index], wheigh[index]);
(*gmax) += wheigh[index];
// printf("GMAX == %d\n", (*gmax));
swap (high, (*n), index);
swap (wheigh, (*n), index);
(*n)--; nr--;
(*h) -= u;
// printVec (high, (*n));
// printVec (wheigh, (*n));
}
// h = temp; // h = h - (u * nr);
// printf ("%d %d %d %d\n", temp, nr, (*h), (*gmax));
}
int main ()
{
int n, h, u;
int *high, *wheigh;
FILE *fin, *fout;
int i, poz, nrCulegeri;
int gmax = 0;
fin = fopen ("gutui.in", "r");
if (fin == NULL)
{
printf("reading error!\n");
exit(0);
}
fout = fopen ("gutui.out", "w");
fscanf(fin, "%d %d %d", &n, &h, &u);
high = (int*)malloc (n * sizeof (int));
wheigh = (int*)malloc (n * sizeof (int));
for (i = 0; i < n; i++)
{
fscanf(fin, "%d %d", &high[i], &wheigh[i]);
}
// printVec (high, n);
// printVec (wheigh, n);
while (n >= 0)
{
// printf("Caut gutui\n");
// printf("H = %d N = %d\n", h, n);
// printVec (high, n);
// printVec (wheigh, n);
poz = findMax(wheigh, high, n, 0, h);
if (poz == -1)
{
break;
}
nrCulegeri = functionX (high, wheigh, &n, poz, &h, u, &gmax);
// printf ("%d ", high[poz]);
}
// printf ("%d %d\n", h, n);
// printf("Am cules %dkg\n", gmax);
// printf("Au ramas\n");
// printVec (high, n);
// printVec (wheigh, n);
fprintf (fout, "%d\n", gmax);
fclose (fin);
fclose (fout);
return 0;
}