Cod sursa(job #271658)
#include <stdio.h>
const int N_MAX = 100010;
int C[N_MAX], P[N_MAX], din[N_MAX];
struct deque {
int el, val;
} dq[N_MAX];
int main()
{
freopen("branza.in", "r", stdin);
#ifndef _SCREEN_
freopen("branza.out", "w", stdout);
#endif
int N, S, T;
scanf("%d %d %d\n", &N, &S, &T);
for (int i = 1; i <= N; i ++) {
scanf("%d %d\n", &C[i], &P[i]);
}
din[1] = C[1];
int in = 1, sf = 1;
dq[1].val = C[1] + (N - 1) * S;
dq[1].el = 1;
for (int i = 2; i <= N; i ++) {
while (i - dq[in].el > T) in ++;
while (sf >= in && (C[i] + (N - i) * S < dq[sf].val)) sf --;
dq[++ sf].val = C[i] + (N - i) * S;
dq[sf].el = i;
din[i] = dq[in].val - (N - i) * S;
}
long long rez = 0;
for (int i = 1; i <= N; i ++) {
rez += (long long) P[i] * din[i];
}
printf("%lld\n", rez);
return 0;
}