```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
long long sumt[300005],sumc[300005],f[300005];
long long s;
int que[300005];
int n;
long long sum(int a,int b)
{
return sumc[a]-sumc[b];
}
long long g(int j1,int j2)
{
return (f[j2]-f[j1]-s*sumc[j2]+s*sumc[j1]);
}
long long g1(int j1,int j2)
{
return sumc[j1]-sumc[j2];
}
int ef(int l,int r,long long p)
{
while(l<r)
{
int mid=(l+r)>>1;
if((ll)g(que[mid],que[mid+1])>=(ll)p*(ll)g1(que[mid+1],que[mid])) r=mid;
else l=mid+1;
}
return r;
}
int main()
{
scanf("%d",&n);
scanf("%lld",&s);
int t,c;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&t,&c);
sumt[i]=sumt[i-1]+(ll)t;
sumc[i]=sumc[i-1]+(ll)c;
}
int head=1,tail=1;
que[head]=0;f[0]=0;
for(int i=1;i<=n;i++)
{
t=ef(head,tail,sumt[i]);
f[i]=(ll)f[que[t]]+(ll)sumt[i]*(ll)sum(i,que[t])+(ll)s*(ll)sum(n,que[t]);
while(head<tail && (ll)g(que[tail],i)*(ll)g1(que[tail],que[tail-1])<=(ll)g(que[tail-1],que[tail])*(ll)g1(i,que[tail]))
tail--;
tail++;que[tail]=i;
}
cout<<(ll)f[n]<<endl;
}
```
by 菜鸟让让我 @ 2018-07-21 23:24:38