#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long int N; //numar gutui
long int H; //inaltimea maxima la care ajunge gigel
long int U; //inaltimea cu care se ridica gutuiele, dupa ce a cules o gutuie
long int** citire () {
FILE *in;
long int **linie;
long int linie_curenta = 0, i;
if ( (in = fopen("gutui.in", "r") ) == NULL) {
printf("Nu am putut deschide fisierul de intrare.\n");
exit(1);
} else {
fscanf(in,"%li %li %li",&N,&H,&U);
linie = (long int**) malloc( (N+1) * sizeof(long int*) ); //aloc memorie initial pentru toata structura
linie[linie_curenta] = (long int*)malloc(3*sizeof(long int)); //aloc memorie pentru prima linie
for (i=0;i<N;i++) {
fscanf(in, "%li %li", &linie[linie_curenta][0], &linie[linie_curenta][1] ); //citesc linie cu linie
linie_curenta++; //trec la linia urmatoare
linie[linie_curenta] = (long int*)malloc(3*sizeof(long int)); //aloc memorie pentru linia urmatoare
}
}
fclose(in);
return linie;
}
void afisare(long int g) {
FILE *out;
if ( (out = fopen("gutui.out", "w") ) == NULL) {
printf("Nu am putut deschide fisierul de iesire.\n");
exit(1);
} else {
fprintf(out,"%li", g);
}
fclose(out);
}
void swap(long int *x,long int *y)
{
long int temp;
temp = *x;
*x = *y;
*y = temp;
}
void quicksort_array(long int list[],long int m,long int n)
{
long int key,i,j,k;
if( m < n)
{
k = (m+n)/2;
swap(&list[m],&list[k]);
key = list[m];
i = m+1;
j = n;
while(i <= j)
{
while((i <= n) && (list[i] <= key))
i++;
while((j >= m) && (list[j] > key))
j--;
if( i < j)
swap(&list[i],&list[j]);
}
// swap two elements
swap(&list[m],&list[j]);
// recursively sort the lesser list
quicksort_array(list,m,j-1);
quicksort_array(list,j+1,n);
}
}
void quicksort(long int **list,long int m,long int n)
{
long int key,i,j,k;
if( m < n)
{
k = (m+n)/2; //alegem pivot
swap(&list[m][0],&list[k][0]);
swap(&list[m][1],&list[k][1]);
key = list[m][0];
i = m+1;
j = n;
while(i <= j)
{
while((i <= n) && (list[i][0] <= key))
i++;
while((j >= m) && (list[j][0] > key))
j--;
if( i < j) {
swap(&list[i][0],&list[j][0]);
swap(&list[i][1],&list[j][1]);
}
}
// swap two elements
swap(&list[m][0],&list[j][0]);
swap(&list[m][1],&list[j][1]);
// recursively sort the lesser list
quicksort(list,m,j-1);
quicksort(list,j+1,n);
}
}
void printlist(long int **list,long int n)
{
long int i,j;
for(i=0;i<n;i++) {
for(j=0;j<2;j++)
printf("%li ",list[i][j]);
printf("\n");
}
}
int main() {
long int **mat;
long int i,j,pas_curent = 0;
long int greutate_maxima = 0;
long int v[N]; //vector de solutii partiale, in care memoram greutatile gutuilor, in ordine crescatoare
v[0] = 0;
mat = citire (); //citim datele. mat[i][0] ->inaltimea. mat[i][1] -> greutatea
quicksort(mat,0,N-1); //ordonam gutuile dupa inaltimea la care se afla initial
for( i =N-1; i>=0; i--) {
if ( ( (H - mat[i][0]) / U ) >= pas_curent ) {
//inserez si sortez
v[pas_curent++] = mat[i][1] ;
quicksort_array(v,0,pas_curent-1);
} else {
if ( mat[i][1] >= v[0] ) {
//scot primul element
//inserez si sortez
v[0] = mat[i][1];
quicksort_array(v,0,pas_curent-1);
}
}
}
for ( j = 0; j <= pas_curent; j++ ) {
greutate_maxima+=v[j];
}
afisare(greutate_maxima);
return 0;
}