#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct info {
unsigned long h, w;
} *v;
unsigned long u;
int comp(const void *a, const void *b)
{
struct info l1, l2;
l1 = *((struct info *) a);
l2 = *((struct info *) b);
if (l2.h / u >= l1.h / u) {
if (l2.h / u > l1.h / u)
return 1;
else
return l2.w - l1.w;
}
else {
return -1;
}
}
inline unsigned long min(unsigned long a, unsigned long b)
{
return ((a < b) ? a : b);
}
inline unsigned long max(unsigned long a, unsigned long b)
{
return ((a > b) ? a : b);
}
int main()
{
unsigned long n, h, index, size, sum, steps, lastquantity, quantity, nextindex, groupitems;
unsigned int i, j, k;
FILE *in, *out;
unsigned long *a;
in = fopen("gutui.in", "rt");
out = fopen("gutui.out", "wt");
fscanf(in, "%lu %lu %lu", &n, &h, &u);
v = (struct info *) malloc(n * sizeof(struct info));
for (i = 0, size = 0; i < n; i++) {
fscanf(in , "%lu %lu", &v[size].h, &v[size].w);
if (v[size].h <= h)
size++;
}
a = (unsigned long *) malloc(((h - v[size - 1].h) / u + 1 + 1) * sizeof(unsigned long));
qsort(v, size , sizeof(struct info), comp);
for (i = 0 ; i < ((h - v[size - 1].h) / u + 1 + 1); i++) a[i] = 0;
a[0] = 0;
steps = (h - v[0].h) / u + 1;
nextindex = 0;
while (((h - v[nextindex].h) / u + 1) == steps && nextindex < size)
nextindex++;
lastquantity = min(steps, nextindex);
quantity = lastquantity;
for (i = 1, sum = 0; i <= lastquantity; i++) {
a[i] = v[i - 1].w + sum;
sum += v[i - 1].w;
}
index = nextindex;
if (index < size)
while (0 < 1) {
steps = (h - v[index].h) / u + 1;
//calculate where the next group starts and finding the number of elements for the current group
nextindex = index;
while (((h - v[nextindex].h) / u + 1) == steps && nextindex < size)
nextindex++;
groupitems = nextindex - index;
quantity = lastquantity + min(steps - lastquantity, groupitems);
//printf("Checking : indexes from %lu - %lu , quantity %lu\n", index, nextindex, quantity);
//determine maximum weight for quantity > lastquantity
if (quantity > lastquantity) {
for (i = 0; i < min(quantity - lastquantity, groupitems); i++) {
//printf("Intra in bucla\n");
for (j = 0, sum = 0 ; j < i; j++) sum += v[index + j].w;
for (k = 0; k <= min(lastquantity , groupitems - 1 - i); j++, k++) {
//printf("Intra in a doua bucla\n");
//printf("a[%lu] ( = %lu) = max (a[%lu] ( = %lu), a[%lu] ( = %lu) + %lu + v[%lu].w ( = %lu)\n", lastquantity + i + 1, a[lastquantity + i + 1], lastquantity + i + 1, a[lastquantity + i + 1], lastquantity - k, a[lastquantity - k], sum, index + j, v[index + j].w);
a[lastquantity + i + 1] = max(a[lastquantity + i + 1], a[lastquantity - k] + sum + v[index + j].w);
//printf("%lu\n", a[lastquantity + i + 1]);
sum += v[index + j].w;
}
}
}
for (i = lastquantity; i > 0; i--) {
for (k = 0, sum = 0; k <= min(i - 1, groupitems - 1); k++) {
a[i] = max(a[i], a[i - k - 1] + sum + v[index + k].w);
sum += v[index + k].w;
}
}
if (nextindex == size)
break;
lastquantity = max(lastquantity, quantity);
index = nextindex;
//for (i = 0; i <= lastquantity; i++) printf("%lu ", a[i]);
//printf("\n");
}
fprintf(out, "%lu", a[quantity]);
/* for (i = 0; i < n; i++)
printf("(%lu %lu)", v[i].h, v[i].w);*/
free(a);
free(v);
fclose(in);
fclose(out);
return 0;
}