//UNGUREANU CRISTIAN 324CA
//TEMA 1 PA - GUTUI
#include <stdio.h>
// nr gutui, inaltimea maxima, inaltarea, rezultatul final
long n, hi, u, smax;
// inantimea fiecarei gutui si greutatea
long h[100001], w[100001];
long h1[100001], w1[100001], i, j, k, l, imin; // vectori auxiliari si alte variabile
//functii pentru quicksort
void swap(long *x, long *y)
{
long auxi;
auxi = *x;
*x = *y;
*y = auxi;
}
long pivot(long i, long j)
{
return((i+j)/2);
}
void quicksort(long m, long n)
{
long i, j, k, l;
if( m<n)
{
k = pivot(m, n);
swap(&h[m], &h[k]);
swap(&w[m], &w[k]);
l = h[m];
i = m+1;
j = n;
while(i<=j)
{
while((i<=n) && (h[i]>=l))
i++;
while((j>=m) && (h[j]<l))
j--;
if(i<j)
{
swap(&h[i], &h[j]);
swap(&w[i], &w[j]);
}
}
swap(&h[m], &h[j]);
swap(&w[m], &w[j]);
quicksort(m, j-1);
quicksort(j+1, n);
}
}
int main()
{ //citirea datelor
FILE *f=fopen("gutui.in", "r");
FILE *g=fopen("gutui.out", "w");
fscanf(f, "%ld %ld %ld", &n, &hi, &u);
for(i=0; i<n; i++)
fscanf(f, "%ld %ld", &h[i], &w[i]);
//sortam descrescator fructele, in functie de inaltime
quicksort(0, n-1);
smax=0, k=0;
for(i=0; i<n; i++)// parcurgem fructele, ordonate descrescator dupa inaltime
if(h[i]<=hi) // daca un fruct poate fi cules
{
w1[k]=w[i];
h1[k]=h[i];// il adaugam la vectorul de fructe culese, si greutatea i-o adaugam la castigul total
k++;
smax+=w[i];
if(hi>=u) // in loc sa crestem fiecare inaltime la fiecare pas, scadem u din hi la fiecare pas
hi-=u;
else
hi=0;
}
else // altfel, gasim indicele fructului cu greutate minima din vectorul de fructe culese curent
{
imin=0;
for(j=1; j<k; j++)
if(w1[j]<w1[imin])
imin=j;
if(w[i]>w1[imin]) //daca fructul i e mai greu decat acel fruct, il substituim, modificand si castigul total
{
smax = smax+w[i]-w1[imin];
w1[imin]=w[i];
h1[imin]=h[i];
}
}
// scriem rezultatul
fprintf(g, "%ld", smax);
fclose(f);
fclose(g);
return 0;
}