分析

我们先把最初的 方程写出来。令 为 结尾的最小代价。那么转移为 。那么我们令 是 的决策点，那么用前缀和 那么化简后 ，那么我们把这个化为了 的形式。但是 并不单调，所以我们考虑使用 维护一个上凸壳。时间复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long 
const LL N = 8e5 + 10,mod = 998244353,M = 6e8;
const long long inf = 0x3f3f3f3f3f3f3f3f;
LL read() {
    LL x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f=1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
LL f[N],n,m,S,C[N],T[N];
LL rt,size,t[N],lc[N],rc[N];
LL clac(LL id,LL pos) {return -C[id] * pos + f[id];}
void insert(LL &u,LL l,LL r,LL id) {
    if(!u) u = ++size;
    if(!t[u]) {t[u] = id;return;}
    LL mid = l + r >> 1;
    LL val_L = clac(id,l),val_R = clac(id,r),val_l = clac(t[u],l),val_r = clac(t[u],r);
    if(val_L <= val_l && val_R <= val_r) {t[u] = id;return;}
    if(val_l <= val_L && val_r <= val_R) {return;}
    insert(lc[u],l,mid,id);insert(rc[u],mid+1,r,id);
}
LL query(LL u,LL l,LL r,LL pos) {
    if(!u || !t[u]) return inf;
    LL ans = clac(t[u],pos);
    LL mid = l + r >> 1;
    if(pos <= mid) return min(ans,query(lc[u],l,mid,pos));
    else return min(ans,query(rc[u],mid+1,r,pos));
}
int main() {
    n = read();S = read();
    for(LL i = 1;i <= n;i++) T[i] = T[i-1] + read(),C[i] = C[i-1] + read();
    f[n+1] = 0;C[n+1] = 0;insert(rt,-M,M,n+1);
    for(LL i = 1;i <= n;i++) { 
        LL res = query(rt,-M,M,T[i] + S);
        // if(res >= inf) f[i] = C[n] * S + C[i] * T[i];
        f[i] = res + C[n] * S + C[i] * T[i];
        insert(rt,-M,M,i);
        // cout << res << endl;
    }
    cout << f[n] << endl;
    return 0;
}