#include <stdio.h>
#include <stdlib.h>
struct gut{
unsigned int inalt;
unsigned int greu;
unsigned int index;
};
int compare_in (const void * a, const void * b)
{
if ((*(struct gut*)a).inalt == (*(struct gut*)b).inalt)
return -((*(struct gut*)a).greu - (*(struct gut*)b).greu);
return -((*(struct gut*)a).inalt - (*(struct gut*)b).inalt);
}
int compare_gr (const void * a, const void * b)
{
if ((*(struct gut*)a).greu == (*(struct gut*)b).greu)
return -((*(struct gut*)a).inalt - (*(struct gut*)b).inalt);
return -((*(struct gut*)a).greu - (*(struct gut*)b).greu);
}
unsigned int max_lost (struct gut *gutui_in, unsigned int pas, unsigned int *i, unsigned int n, unsigned int u, unsigned int h, unsigned char * cules){
unsigned int gr = 0, j;
for (j = *i; j < n; j++)
{
if ((gutui_in[j].inalt + pas * u <= h)&&(cules[gutui_in[j].index] == 0))
break;
if ((gutui_in[j].greu > gr)&&(cules[gutui_in[j].index] == 0))
gr = gutui_in[j].greu;
//if (cules[gutui_in[j].index] == 0) printf("pas = %u lost = %u\n", pas, gutui_in[j].index);
cules[gutui_in[j].index] = 1;
}
*i = j;
return gr;
}
unsigned int max_next_lost (struct gut *gutui_in, unsigned int pas, unsigned int i, unsigned int n, unsigned int u, unsigned int h, unsigned char * cules, unsigned int gr){
unsigned int k = 0, j = i, pas1 = pas;
//for (j = i; j < n; j++)
while (j < n)
{
if ((gutui_in[j].inalt + pas1 * u <= h)&&(cules[gutui_in[j].index] == 0))
{
pas1 = pas1 + 1;
k = 0;
//break;
}
else
{
if ((gutui_in[j].greu > gr)&&(cules[gutui_in[j].index] == 0))
//gr = gutui_in[j].greu;
k++;
if ( k >= 2) break;
j++;
//if (cules[gutui_in[j].index] == 0) printf("pas = %u next_lost = %u\n", pas, gutui_in[j].index);
//cules[gutui_in[j].index] = 1;
}
}
//*i = j;
//printf("gr_next_lost %u\n", gr);
//return gr;
return k;
}
int main(){
unsigned int i, j;
FILE *f = fopen("gutui.in","r");
unsigned int n = 0,h = 0 ,u = 0, max = 0, gr;
fscanf(f, "%d", &n);
fscanf(f, "%d", &h);
fscanf(f, "%d", &u);
//struct gut *gutui = (struct gut *)malloc(n * sizeof(struct gut));
unsigned char *cules = (unsigned char *)calloc(n, sizeof(unsigned char));
struct gut *gutui_in = (struct gut *)malloc(n * sizeof(struct gut));
struct gut *gutui_gr = (struct gut *)malloc(n * sizeof(struct gut));
for (i = 0; i < n; i++)
{
fscanf(f, "%u", &gutui_in[i].inalt);
fscanf(f, "%u", &gutui_in[i].greu);
gutui_gr[i].inalt = gutui_in[i].inalt;
gutui_gr[i].greu = gutui_in[i].greu;
gutui_in[i].index = i;
gutui_gr[i].index = i;
}
fclose(f);
qsort(gutui_in, n, sizeof(struct gut), compare_in);
qsort(gutui_gr, n, sizeof(struct gut), compare_gr);
/*for (i = 0; i < n; i++)
{
printf("%u ", gutui_in[i].index);
printf("%u ", gutui_in[i].inalt);
printf("%u\n", gutui_in[i].greu);
}
printf("\n");
for (i = 0; i < n; i++)
{
printf("%u ", gutui_gr[i].index);
printf("%u ", gutui_gr[i].inalt);
printf("%u\n", gutui_gr[i].greu);
}*/
/*i = 0;
printf("%u\n", max_lost(gutui_in, 1, &i, n, u, h, cules));
for (j = 0; j < n; j++) printf("%d", cules[j]);
printf("\n");
printf("%u\n", max_lost(gutui_in, 2, &i, n, u, h, cules));
for (j = 0; j < n; j++) printf("%d", cules[j]);*/
unsigned int pas = 1, max1, max2, max3, k;
i = 0;
j = 0;
while (j < n)
if (cules[gutui_gr[j].index] == 1) j++;
else
{
max1 = 0;
max2 = 0;
max3 = 0;
//printf("max1 = %u\n", max1);
//printf("j = %u\n", j);
while ((cules[gutui_gr[j].index] == 1)&&(j < n)) j++;
//printf("j = %u\n", j);
max1 = max_lost(gutui_in, pas, &i, n, u, h, cules);
if (j < n) {
max2 = gutui_gr[j].greu;
//printf("max2 = %u\n", max2);
//k = j + 1;
/*while ((cules[gutui_gr[k].index] == 1)&&(k < n)) k++;
if (k < n) max3 = gutui_gr[k].greu;*/
if (max1 != 0) max3 = max_next_lost(gutui_in, pas + 1, i, n,u,h, cules, max1);
//printf("max3 = %u\n", max3);
}
//if (max1 > max3) max = max + max1;
if ((max3 < 2)&&(max1 != 0)) max = max + max1;
else
{
max = max + max2;
if (j < n) cules[gutui_gr[j].index] = 1;
}
//for (k = 0; k < n; k++) printf("%d", cules[k]);
//printf("\n");
pas = pas + 1;
}
//printf("%d\n", max);
f = fopen("gutui.out","w");
fprintf(f,"%u\n", max);
fclose(f);
return 0;
}