When the final sum of the heights of upper and lower teeth \(H\) is fixed, the total cost is \(\displaystyle\sum _ {i=1} ^ N(U _ i+D _ i)-NH\), independent of how the teeth are ground (because paying one yen always reduce the sum by one).
Therefore, it is sufficient to find the maximum feasible \(H\).

If an \(H\) is feasible, then any \(H ^ \prime\) with \(H ^ \prime\lt H\) is always feasible. (This can be achieved by starting from the state with the height sum \(H\), grinding the lower teeth as much as possible, and once it becomes impossible, grinding the upper teeth.) Thus, if one can determine fast enough if a given \(H\) is feasible, the problem can be solved by binary search.

Given a fixed \(H\), we need to solve the following problem:

You are given a sequence of intervals \(([L _ 1,R _ 1],[L _ 2,R _ 2],\ldots,[L _ N,R _ N])\). Determine if there is an integer sequence \((A _ 1,A _ 2,\ldots,A _ N)\) such that:

• \(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)\).

This can be determined in a total of \(O(N)\) time by scanning them from the left while maintaining the range of possible \(A _ i\).

Thus, the problem has been solved.

The sample code follows.

#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) {
        // Check if the range of possible upper teeth is non-empty
        unsigned interval_L{}, interval_R{H};
        for (const auto& [U, D] : teeth) {
            // If we denote the previous segment by [L, R],
            // what we want is the intersection of:
            // - [L - X, R + X] (the distance is not greater than X), and
            // - [H - D, U] (obtainable by grinding).
            interval_L = max({interval_L + D, H + X, X + D}) - X - D;
            interval_R = min(interval_R + X, U);

            // Return false once it becomes empty
            if (interval_L > interval_R)
                return false;
        }
        return true;
    }};

    // H can never exceed U[i] + D[i]
    unsigned R{ranges::min(teeth | views::transform([](const auto& tooth) { return tooth.first + tooth.second; })) + 1};
    // If H is not greater than X and not greater than any U[i] + D[i], it is conforming
    unsigned L{min(X, R - 1)};

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

    // The answer is ∑ (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;
}