Code : Merchant Takahashi

#include <bits/stdc++.h>
using namespace std;

const long long inf = 1e18;

void solve() {
    int n, m;
    long long c;
    cin >> n >> c >> m;

    // dp[i] is the maximum profit that you can gain with the markets seen so
    // far such that you are currently in the i-th market.
    vector<long long> dp(n, -inf);
    dp[0] = 0;

    for (int j = 0; j < m; j++) {
        int t;
        long long p;
        cin >> t >> p;
        t--;

        auto ndp = dp;
        for (int i = 0; i < n; i++) {
            ndp[t] = max(ndp[t], dp[i] - c * abs(i - t) + p);
        }
        swap(dp, ndp);
    }
    cout << *max_element(dp.begin(), dp.end()) << endl;
}

int main() { solve(); }

#include <bits/stdc++.h>
using namespace std;

const long long inf = 1e18;

void solve() {
    int n, m;
    long long c;
    cin >> n >> c >> m;

    // dp[i] is the maximum profit that you can gain with the markets seen so
    // far such that you are currently in the i-th market.
    vector<long long> dp(n, -inf), ldp(n, -inf), rdp(n, -inf);
    dp[0] = 0, ldp[0] = 0, rdp[0] = 0;

    // ldp[i] = dp[i] + c*i
    // rdp[i] = dp[i] - c*i

    for (int j = 0; j < m; j++) {
        int t;
        long long p;
        cin >> t >> p;
        t--;

        auto ndp = dp;
        for (int i = 0; i < t; i++) {
            ndp[t] = max(ndp[t], ldp[i] + p - c * t);
        }
        for (int i = t; i < n; i++) {
            ndp[t] = max(ndp[t], rdp[i] + p + c * t);
        }

        swap(dp, ndp);
        ldp[t] = dp[t] + c * t;
        rdp[t] = dp[t] - c * t;
    }

    cout << *max_element(dp.begin(), dp.end()) << endl;
}

int main() { solve(); }

#include <atcoder/segtree.hpp>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

const long long inf = 1e18;

long long op(long long a, long long b) { return max(a, b); }
long long e() { return -inf; }

void solve() {
    int n, m;
    long long c;
    cin >> n >> c >> m;

    // dp[i] is the maximum profit that you can gain with the markets seen so
    // far such that you are currently in the i-th market.
    segtree<long long, op, e> dp(n), ldp(n), rdp(n);
    dp.set(0, 0), ldp.set(0, 0), rdp.set(0, 0);

    for (int j = 0; j < m; j++) {
        int t;
        long long p;
        cin >> t >> p;
        t--;

        long long mx = dp.get(t);
        mx = max(mx, ldp.prod(0, t) + p - c * t);
        mx = max(mx, rdp.prod(t, n) + p + c * t);

        dp.set(t, mx);
        ldp.set(t, dp.get(t) + c * t);
        rdp.set(t, dp.get(t) - c * t);
    }

    cout << dp.all_prod() << endl;
}

int main() { solve(); }