#include <stdio.h>
int *openFile(char *fileName, int *h, int *w, int *N, int *H, int *U)
{
FILE *file = NULL;
int i;
file = fopen(fileName, "r+");
if (file == NULL)
{
printf("%s does not exist.\n", fileName);
return 0;
}
fscanf(file, "%i%i%i", N, H, U);
for (i=0; i<*N; ++i)
{
fscanf(file, "%i", &h[i]);
fscanf(file, "%i", &w[i]);
}
fclose(file);
return 1;
}
int fileWrite(char *fileName, int max)
{
FILE *file = NULL;
file = fopen(fileName, "w+");
if (file == NULL)
{
printf("Could not create file.\n");
return 0;
}
fprintf(file, "%i", max);
fclose(file);
return 1;
}
void swap(int i, int j, int *h, int *w)
{
int aux = h[i];
h[i] = h[j];
h[j] = aux;
aux = w[i];
w[i] = w[j];
w[j] = aux;
}
int partition(int left, int right, int *h, int *w)
{
int i, j, x = h[left];
i = left;
for(j = left + 1; j <= right; j++)
if(h[j] > x)
{
i = i + 1;
swap(i, j, h, w);
}
swap(left, i, h, w);
return i;
}
void qsort(int left, int right, int *h, int *w)
{
int pos;
if(left >= right)
return;
pos = partition(left, right, h, w);
qsort(left, pos - 1, h, w);
qsort(pos + 1, right, h, w);
}
int min(int a, int b)
{
return a>b?b:a;
}
int main()
{
int N, H, U;
int x, max, t[10000]={0};
int w[10000]={0}, h[10000]={0};
int i, j;
openFile("gutui.in", h, w, &N, &H, &U);
qsort(0, N, h, w);
t[1] = w[0];
max = w[0];
for(i = 1; i < N; ++i)
{
x = (H - h[i]) / U;
for(j = min(i, x) + 1; j >= 1; --j)
{
if(t[j - 1] + w[i] > t[j])
{
t[j] = t[j - 1] + w[i];
if(t[j] > max)
max = t[j];
}
}
}
fileWrite("gutui.out", max);
return 0;
}