最終的な上下の歯の高さの和 \(H\) を固定したとき、支払う金額は \(\displaystyle\sum _ {i=1} ^ N(U _ i+D _ i)-NH\) であり、具体的な削り方によりません（\(1\) 円を支払うと高さの総和は必ず \(1\) だけ減少します）。 よって、条件を満たすような削り方ができる最大の \(H\) を求めたいです。

ある \(H\) で条件を満たすことができる場合、\(H ^ \prime\lt H\) なる \(H ^ \prime\) でも満たすことができます（\(H\) を実現する状態からなるべく下の歯を削り、削れなくなったら上の歯を削るようにすることで具体的に構成できます）。 このことから、 \(H\) を固定したときに条件を満たせるかを高速に判定できれば、二分探索を行うことでこの問題を解くことができます。

\(H\) を固定したとき、次の問題を解くことになります。

区間の列 \(([L _ 1,R _ 1],[L _ 2,R _ 2],\ldots,[L _ N,R _ N])\) が与えられる。 整数列 \((A _ 1,A _ 2,\ldots,A _ N)\) であって、次の条件を満たすものが存在するか判定せよ。

• \(L _ i\leq A _ i\leq R _ i\ (1\leq i\leq N)\)
• \(\vert A _ i-A _ {i+1}\vert\leq X\ (1\leq i\lt N)\)

これは、左から見て \(A _ i\) がとりうる範囲を区間で持つことで \(O(N)\) 時間で判定ができます。

以上でこの問題を解くことができました。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>
#include <numeric>

int main() {
    using namespace std;
    unsigned N, X;
    cin >> N >> X;

    vector<pair<unsigned, unsigned>> teeth(N);
    for (auto&& [U, D] : teeth)
        cin >> U >> D;

    const auto check{[X, &teeth](const unsigned H) {
        // 上の歯が存在できる区間が空にならないか調べる
        unsigned interval_L{}, interval_R{H};
        for (const auto& [U, D] : teeth) {
            // 直前の区間を [L, R] として
            // - 距離が X 以下 : [L - X, R + X]
            // - 削ってできる : [H - D, U]
            // の共通部分が求めるもの
            interval_L = max({interval_L + D, H + X, X + D}) - X - D;
            interval_R = min(interval_R + X, U);

            // 空になったら false
            if (interval_L > interval_R)
                return false;
        }
        return true;
    }};

    // H は U[i] + D[i] より大きくはできない
    unsigned R{ranges::min(teeth | views::transform([](const auto& tooth) { return tooth.first + tooth.second; })) + 1};
    // H が X 以下かつすべての U[i] + D[i] 以下ならかならず条件を満たす
    unsigned L{min(X, R - 1)};

    while (L + 1 < R) {
        const auto M{(L + R) / 2};
        (check(M) ? L : R) = M;
    }

    // ∑ (U[i] + D[i]) - LN が答え
    cout << transform_reduce(begin(teeth), end(teeth), 0UL, plus{}, [](const auto& tooth) { return tooth.first + tooth.second; }) - static_cast<unsigned long>(L) * N << endl;
    return 0;
}