设 $f(i,v)$ 为处理完前 $i$ 堆泥土且结余 $v$ 单位泥土的最小成本。问题的答案就是 $f(n,0)$。

可以写出状态转移方程：

其中，

是用于补足第 $i$ 堆泥土的亏空（或盈余）（即 $(b_i-a_i)-(w-v)$）的成本，而 $|w|Z$ 是将前一次剩余（或缺少）的土方搬到当前位置的新增成本。

方程只涉及分段线性的凸函数，因此考虑使用 slope trick。

在 $f(i-1,w)$ 的基础上：

• 加 $|w|Z$ 相当于在原点左侧的斜率都减去 $Z$，在原点右侧的斜率都加上 $Z$；
• 不考虑 $(b_i-a_i)$ 项，后面就是 $h(v-w)$，将它与 $f(i-1,w)+|w|Z$ 的和取 $w$ 的最小值，相当于做 Minkowski 和，结果就是将 $f(i-1,w)+|w|Z$ 的所有斜率（即差分）与 $-Y$ 取最大值，与 $X$ 取最小值；
• 最后，在得到的函数的基础上再加上 $b_i-a_i$ 项相当于将它向左平移 $b_i-a_i$ 的单位。

基于这些分析，只需要维护原点左右两侧离原点最近的几个斜率的值即可，事实上只需要两个栈。整体的操作用懒标记，左右移动只需要将栈顶的元素移动一下。

因为更远处的斜率一定为 $-Y$ 或 $X$，所以不必记录，当左侧或右侧的栈空了的时候直接补相应的值即可。

最后的答案是 $0$ 处的取值，所以在左右移动时需要更新答案。

复杂度是 $O(n\max\{a,b\})$ 的。

核心代码如下：

int main() {
    int n;
    long long x, y, z;
    std::cin >> n >> x >> y >> z;
    std::stack<long long> neg, pos;
    long long lt = 0, rt = 0;
    long long res = 0;
    for (; n; --n) {
        int a, b;
        std::cin >> a >> b;
        lt -= z;
        rt += z;
        for (; b < a; ++b) {
            auto l = -y;
            if (!neg.empty()) {
                l = std::max(l, neg.top() + lt);
                neg.pop();
            }
            pos.emplace(l - rt);
            res -= l;
        }
        for (; b > a; --b) {
            auto r = x;
            if (!pos.empty()) {
                r = std::min(r, pos.top() + rt);
                pos.pop();
            }
            neg.emplace(r - lt);
            res += r;
        }
    }
    std::cout << res;
    return 0;
}