#include <fstream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#define INF 100000
using namespace std;
bool minim(int i, int j)
{
return (i > j);
}
int partition(int *a, int *b, int p, int r)
{
int i, j, x, y;
x = a[r];
y = b[r];
i = p - 1;
for(j = p; j < r; j++)
if((a[j] > x) || (a[j] == x && b[j] > y))
{
i++;
swap(a[i], a[j]);
swap(b[i], b[j]);
}
swap(a[i+1], a[r]);
swap(b[i+1], b[r]);
return (i + 1);
}
void quicksort(int *a,int *b, int p, int r)
{
if(p < r)
{
int q = partition(a, b, p, r);
quicksort(a, b, p, q - 1);
quicksort(a, b, q + 1, r);
}
}
int main()
{
int n, h, u; // nr. gutui, inaltime maxima, cu cat se ridica crengile
int nn, hh, ww;
int i, min;
int *weight, *height, *NrGutui, *Sol;
vector<int> v;
ifstream in("gutui.in");
ofstream out("gutui.out");
in >> nn;
in >> h;
in >> u;
weight = (int *)malloc(nn * sizeof(int));
height = (int *)malloc(nn * sizeof(int));
n = 0;
for(i = 0; i < nn; i++)
{
in >> hh; in >> ww;
if(hh <= h)
{
height[n] = hh;
weight[n] = ww;
n++;
}
}
// Sortez descrescator perechile (inaltime, greutate) dupa inaltime
quicksort(height, weight, 0, n - 1);
Sol = (int *)malloc(n * sizeof(int));
NrGutui = (int*)malloc(n * sizeof(int));
// sol[i] = greutatea maxima ce poate fi culeasa folosind primele i gutui in ordine descrescatoare a inaltimii
// NrGutui[i] = numarul de gutui culese din primele i gutui in ordine descrescatoare a inaltimii
Sol[0] = weight[0];
NrGutui[0] = 1;
v.push_back(weight[0]);
make_heap(v.begin(), v.end(), minim);
for(i = 1; i < n; i++)
{
// Gutuia i poate fi culeasa daca
// inaltimea initiala la care se afla gutuia + cat s-a ridicat creanga dupa ce am cules NrGutui[i] gutui ( inaltimea la care a ajuns depaseste inaltimea maxima )
// nu depaseste inaltimea la care poate ajunge Gigel
if((height[i] + NrGutui[i - 1] * u) <= h)
{
Sol[i] = Sol[i - 1] + weight[i];
NrGutui[i] = NrGutui[i - 1] + 1;
v.push_back(weight[i]);
push_heap(v.begin(), v.end(), minim);
}
else
{
// Gutuia i nu poate fi culeasa
NrGutui[i] = NrGutui[i - 1];
Sol[i] = Sol[i - 1];
// Incerc sa renunt la una dintre gutuile culese pana la pasul i
// astfel incat daca as renunta la ea si ai culege gutuia i, as avea o greutate totala culeasa mai mare
// Gutuia cu greutatea cea mai mica dintre gutuile culese pana la pasul i
min = v.front();
if(min < weight[i])
{
Sol[i] = Sol[i - 1] - min + weight[i];
pop_heap(v.begin(), v.end(), minim);
v.pop_back();
v.push_back(weight[i]);
push_heap(v.begin(), v.end(), minim);
}
}
}
// Greutatea maxima ce poate fi culeasa
out<<Sol[n - 1];
in.close();
out.close();
return 0;
}