Cod sursa(job #68692)
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
#define FIN "branza.in"
#define FOUT "branza.out"
#define p1 first
#define p2 second
int n, s, t;
priority_queue < pair<int, int>, vector<pair<int,int> >, greater<pair<int, int> > > Q;
void citire()
{
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
scanf("%d %d %d", &n, &s, &t);
}
void rez()
{
int i, c, p, cv;
long long final = 0;
// pentru a vedea care este costul minim daca as lua din una din zilele precedente, bagam intr-un heap
// fiecare zi precedenta.. (si scoatem alea pt care "zi" < i-t)
// si pt fiecare costul va fi s*(i-"zi") + costul_zilei_aleia...
// cand bag pe prosti in heap, le pun dif. de timp = -i
for (i=0; i<n; ++i) {
scanf("%d %d", &c, &p);
//fprintf(stderr, " > %d: top=(%d, %d) ", i, Q.top().first, Q.top().second);
while (!Q.empty() && Q.top().second < i - t)
Q.pop();
if (!Q.empty())
cv = min( Q.top().first + i * s, c );
else cv = c;
//fprintf(stderr, "cv=%d ", cv);
Q.push(make_pair(c - s*i, i));
//fprintf(stderr, " --- (%d, %d)\n", c-s*i, i);
final += (long long) cv * p;
}
printf("%lld\n", final);
}
int main()
{
citire();
rez();
return 0;
}