Pagini recente » Cod sursa (job #463560) | Cod sursa (job #2681716) | Cod sursa (job #804630) | Cod sursa (job #789895) | Cod sursa (job #1806467)
#include<bits/stdc++.h>
#define maxN 100005
using namespace std;
int n,s,t,m[maxN],v[maxN],c[maxN],l,st,dr;
int q[2*maxN+5];
long long sol;
int main()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%d%d%d",&n,&s,&t);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&c[i],&v[i]);
}
m[1]=c[1];
st=1;
dr=1;
q[st]=1;
l=t;
for(int i=2;i<=n;i++)
{
while(st<=dr && q[st]<=(i-l)) st++;
while(st<=dr && ((m[q[dr]]+s*(i-q[dr]))>=c[i])) dr--;
if(st<=dr) m[i]=m[q[st]]+s*(i-q[st]);
else
{
m[i]=c[i];
q[++dr]=i;
}
}
for(int i=1;i<=n;i++)
{
sol=sol+1LL*m[i]*v[i];
}
printf("%lld\n",sol);
return 0;
}