高橋君の移動は、高橋君が参加する市場が開催される町を順に移動するものだけを考えて構いません（そうでない移動に対して、余計な停止を取り除くことで最終的な所持金が減ることはありません）。

よって、\(\operatorname{dp}[i]\coloneqq{}\)高橋君が最後に参加した市場が町 \(i\) で行われたときの所持金の最大値 のように定め、これを更新していくことを考えます。 はじめ、\(\operatorname{dp}[1]=10 ^ {10 ^ {100}},\operatorname{dp}[i]=0\ (i\neq1)\) です（便宜上、はじめに \((T _ i,P _ i)=(1,0)\) なる市場に参加したとします）。

市場の情報 \((T _ i,P _ i)\) に対して、更新は次のように行われます。

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

この式を整理します。

\[\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}\]

よって、数列に対して

• 一点更新（chmax）
• prefix max を求める

が高速にできれば、この問題を解くことができます（\((\operatorname{dp}[j]-Cj) _ {1\leq j\leq N}\) の列は前後反転しているとみればよいです）。

これは、セグメント木や fenwick 木などを用いるとクエリ \(O(\log N)\) で、prefix max が切り替わる点列を平衡二分探索木などで管理するとクエリ \(O(\log\min\lbrace N,M\rbrace)\) で処理することができます。

実装例は以下のようになります。セグメント木を用いるものと、prefix max が切り替わる点列を管理するものの両方を示します。

実装の際には、\(10 ^ {10 ^ {100}}\) は少々大きいため、計算結果に影響がない範囲で初期値を調節する必要があります。

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

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

    // range max を求めるセグメント木
    using range_max = atcoder::segtree<unsigned long, [](auto a, auto b){return max(a, b);}, []{return 0UL;}>;

    // (i, dp[i] + Ci) の prefix max を管理するセグメント木と、
    // (i, dp[i] - Ci) の suffix max を管理するセグメント木
    range_max prefix(N), suffix(N);
    
    // 初期値をオーバーフローを起こさない程度の値に設定
    constexpr unsigned long offset{2000000000000000000};
    
    // dp[0] = offset に対応
    prefix.set(0, offset);
    suffix.set(0, offset);
    
    // これまでの所持金の最大値
    unsigned long ans{offset};
    
    for (unsigned i{}; i < M; ++i) {
        unsigned T;
        unsigned long P;
        cin >> T >> P;
        --T;
        
        // dp[i] + Ci のうち i が T 以下であるような最大のものと、
        // dp[i] - Ci のうち i が T 以上であるような最小のものをとる
        // 前者の値 - CT と後者の値 + CT の小さくないほうを求めて、更新に用いる
        const auto best{max(prefix.prod(0, T + 1) - C * T, suffix.prod(T, N) + C * T) + P};
        
        // 所持金の最大値を更新
        ans = max(ans, best);
        
        // 更新
        prefix.set(T, best + C * T);
        suffix.set(T, best - C * T);
    }
    
    // 初期値を引いた値が求める答え
    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;

    // (i, dp[i] + Ci) の prefix max を管理する set と、
    // (i, dp[i] - Ci) の suffix max を管理する set
    set<pair<unsigned, unsigned long>> prefix_max, suffix_max;

    // 初期値をオーバーフローを起こさない程度の値に設定
    constexpr unsigned long offset{2000000000000000000};

    // dp[0] = offset に対応
    prefix_max.emplace(0, offset);
    suffix_max.emplace(0, offset);

    // これまでの所持金の最大値
    unsigned long ans{offset};

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

        // (i, dp[i] + Ci) のうち i が T 以下であるような最大の i と、
        // (i, dp[i] - Ci) のうち i が T 以上であるような最小の i をとる
        // 前者の値 - CT と後者の値 + CT の小さくないほうを求めて、更新に用いる
        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};

        // 所持金の最大値を更新
        ans = max(ans, best);

        // T 以降でより大きくないものを削除して、新しい値を追加
        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);

        // T 以前でより大きくないものを削除して、新しい値を追加
        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);
    }

    // 初期値を引いた値が求める答え
    cout << ans - offset << endl;
    return 0;
}