OIG XII - lsn

// https://szkopul.edu.pl/problemset/problem/R-vfYfy9KfYrxIsJ0SHp-oOS/site/?key=statement
// XII MOI — Zawody indywidualne, etap III.
// (MOI -> Młodzieżowa Olimpiada Informatyczna)

#include <iostream>

constexpr int sizik = 1000 * 1001;

long long pref[sizik];
int pref2[sizik];
long long dp[sizik];

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int n, m, c;
    std::cin >> n >> m >> c;

    for (int i = 0; i < m; i++) {
        int a, b, k;
        std::cin >> a >> b >> k;

        pref[a] += k;
        pref2[a] += k;
        pref[b + 1] -= k;
    }

    for (int i = 1; i <= n; i++) {
        pref[i] += pref[i - 1];
    }

    long long ans = 0;

    for (int i = 1; i <= n; i++) {
        dp[i] = c - pref[i];
        dp[i] = std::max(dp[i], dp[i - 1] + c - pref2[i]);
        ans = std::max(ans, dp[i]);
    }

    std::cout << ans << '\n';

    return 0;
}