代码

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N=3e5+5;
int T=1;
int n;
i64 S;
i64 f[N];
i64 st[N],sc[N];
int head=1,tail,p[N];
i64 X(int x) { return sc[x]; }
i64 Y(int x) { return f[x]; }
i64 K(int x) { return S+st[x]; }
int find(i64 x){
    int l=head,r=tail,mid,ret=tail;
    while(l<=r){
        mid=l+r>>1;
        if(Y(p[mid+1])-Y(p[mid])>x*(X(p[mid+1])-X(p[mid]))) r=mid-1,ret=mid;
        else l=mid+1;
    }
    return p[ret];
}
void solve()
{
    cin>>n>>S;
    for(int i=1;i<=n;i++) cin>>st[i]>>sc[i],st[i]+=st[i-1],sc[i]+=sc[i-1];
    p[++tail]=0;
    for(int i=1,j;i<=n;i++){
        j=find(K(i));
        f[i]=f[j]+S*(sc[n]-sc[j])+st[i]*(sc[i]-sc[j]);
        while(head<tail&&(Y(p[tail])-Y(p[tail-1])*(X(i)-X(p[tail]))>=(Y(i)-Y(p[tail]))*(X(p[tail])-X(p[tail-1])))) tail--;
        p[++tail]=i;
    }
    cout<<f[n];
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    while (T--)
        solve();
    return 0;
}