We can safely assume that Takahashi’s tour consists of travel between towns where the markets that Takahashi participates are held. (For a tour that does violate this condition, we can remove redundant stops without reducing final profit.)

Thus, we define DP (Dynamic Programming) as \(\operatorname{dp}[i]\coloneqq{}\) maximum amount of money that Takahashi has if he finally participates in the market at town \(i\) and maintain it. Initially, \(\operatorname{dp}[1]=10 ^ {10 ^ {100}},\operatorname{dp}[i]=0\ (i\neq1)\). (For convenience, we regard he participated in a market with \((T _ i,P _ i)=(1,0)\)).

According to information on a market \((T _ i,P _ i)\), it is updated as follows:

\[\operatorname{dp}[T _ i]=P _ i+\max _ {1\leq j\leq N}\lbrace\operatorname{dp}[j]-C|j-T _ i|\rbrace\]

We deform this expression.

\[\begin{aligned} \operatorname{dp}[T _ i] &=P _ i+\max _ {1\leq j\leq N}\lbrace\operatorname{dp}[j]-C|j-T _ i|\rbrace\\ &=P _ i+\max\Bigl\lbrace\max _ {1\leq j\lt T _ i}\lbrace\operatorname{dp}[j]-C|j-T _ i|\rbrace,\max _ {T _ i\leq j\leq N}\lbrace\operatorname{dp}[j]-C|j-T _ i|\rbrace\Bigr\rbrace\\ &=P _ i+\max\Bigl\lbrace\max _ {1\leq j\lt T _ i}\lbrace\operatorname{dp}[j]-C(T _ i-j)\rbrace,\max _ {T _ i\leq j\leq N}\lbrace\operatorname{dp}[j]-C(j-T _ i)\rbrace\Bigr\rbrace\\ &=P _ i+\max\Bigl\lbrace-CT _ i+\max _ {1\leq j\lt T _ i}\lbrace\operatorname{dp}[j]+Cj\rbrace,CT _ i+\max _ {T _ i\leq j\leq N}\lbrace\operatorname{dp}[j]-Cj\rbrace\Bigr\rbrace\\ \end{aligned}\]

Therefore, this problem can be solved if one can do

• element-wise update (chmax); and
• prefix max retrieval

fast enough. (We can assume that the sequence \((\operatorname{dp}[j]-Cj) _ {1\leq j\leq N}\) is reversed.)

These can be achieved in \(O(\log N)\) time per query with a segment tree or a Fenwick tree, or in \(O(\log\min\lbrace N,M\rbrace)\) time per query by managing the points where the prefix max changes in a balanced binary search tree.

The sample code is below. We introduce two solutions, one using a segment tree and the other that manages the points where the prefix max changes.

On implementation, you need to properly modify the initial value, as \(10 ^ {10 ^ {100}}\) is a bit large.

#include <iostream>
#include <atcoder/segtree>

int main() {
    using namespace std;
    unsigned N;
    cin >> N;
    unsigned long C;
    cin >> C;
    unsigned M;
    cin >> M;

    // Segment tree for range-max retrieval
    using range_max = atcoder::segtree<unsigned long, [](auto a, auto b){return max(a, b);}, []{return 0UL;}>;

    // Segment tree for prefix max of (i, dp[i] + Ci), and
    // Segment tree for suffix max of (i, dp[i] - Ci) 
    range_max prefix(N), suffix(N);
    
    // Set a initial value that does not cause an overflow
    constexpr unsigned long offset{2000000000000000000};
    
    // corresponds to dp[0] = offset
    prefix.set(0, offset);
    suffix.set(0, offset);
    
    // Maximum amount of money got so far
    unsigned long ans{offset};
    
    for (unsigned i{}; i < M; ++i) {
        unsigned T;
        unsigned long P;
        cin >> T >> P;
        --T;
        
        // Find maximum dp[i] + Ci for i greater than or equal to T,
        // and the minimum dp[i] - ci for i less than or equal to T.
        // the maximum of (former - CT) and (latter + CT) is used for update
        const auto best{max(prefix.prod(0, T + 1) - C * T, suffix.prod(T, N) + C * T) + P};
        
        // Update the maximum amount of money
        ans = max(ans, best);
        
        // Update
        prefix.set(T, best + C * T);
        suffix.set(T, best - C * T);
    }
    
    // The sought answer is the value subtracted by the initial value
    cout << ans - offset << endl;
    return 0;
}

#include <iostream>
#include <set>

int main() {
    using namespace std;
    unsigned N;
    unsigned long C;
    unsigned M;
    cin >> N >> C >> M;

    // A set for prefix max of (i, dp[i] + Ci), and
    // A set for suffix max of (i, dp[i] - Ci) 
    set<pair<unsigned, unsigned long>> prefix_max, suffix_max;

    // Set a initial value that does not cause an overflow
    constexpr unsigned long offset{2000000000000000000};

    // corresponds to dp[0] = offset
    prefix_max.emplace(0, offset);
    suffix_max.emplace(0, offset);

    // Maximum amount of money got so far
    unsigned long ans{offset};

    for (unsigned i{}; i < M; ++i) {
        unsigned T;
        unsigned long P;
        cin >> T >> P;
        --T;

        // Find maximum dp[i] + Ci for i greater than or equal to T,
        // and the minimum dp[i] - ci for i less than or equal to T.
        // the maximum of (former - CT) and (latter + CT) is used for update
        const auto best{max([C, T, &prefix_max]{
                                if(const auto it{prefix_max.lower_bound({T + 1, 0})}; it != begin(prefix_max))
                                    return prev(it)->second - C * T;
                                return 0UL;
                            }(), [C, T, &suffix_max]{
                                if(const auto it{suffix_max.lower_bound({T, 0})}; it != end(suffix_max))
                                    return it->second + C * T;
                                return 0UL;
                            }()) + P};

        // Update the maximum amount of money
        ans = max(ans, best);

        // T 以降でより大きくないものを削除して、新しい値を追加
        // Remove smaller (or equal) elements after T, and insert the new value
        auto prefix_upper{prefix_max.lower_bound({T, 0})};
        while (prefix_upper != end(prefix_max) && prefix_upper->second <= best + C * T)
            prefix_upper = prefix_max.erase(prefix_upper);
        prefix_max.emplace_hint(prefix_upper, T, best + C * T);

        // Remove larger (or equal) elements after T, and insert the new value
        auto suffix_lower{suffix_max.lower_bound({T + 1, 0})};
        while (suffix_lower != begin(suffix_max) && prev(suffix_lower)->second <= best - C * T)
            suffix_max.erase(prev(suffix_lower));
        suffix_max.emplace_hint(suffix_lower, T, best - C * T);
    }

    // The sought answer is the value subtracted by the initial value
    cout << ans - offset << endl;
    return 0;
}