#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using P = pair; constexpr int INF = 1001001001; constexpr int mod = 1000000007; // constexpr int mod = 998244353; template inline bool chmax(T& x, T y){ if(x < y){ x = y; return true; } return false; } template inline bool chmin(T& x, T y){ if(x > y){ x = y; return true; } return false; } template struct SegmentTree{ using F = function; int sz; vector seg; const F f; const Monoid M1; SegmentTree(const F f, const Monoid& M1) : f(f), M1(M1) {} SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) { sz = 1; while(sz < n) sz <<= 1; seg.assign(2 * sz, M1); } void resize(int n){ sz = 1; while(sz < n) sz <<= 1; seg.assign(2 * sz, M1); } void set(int k, const Monoid &x){ seg[k + sz] = x; } void build(){ for(int k = sz - 1; k > 0; --k){ seg[k] = f(seg[k << 1], seg[k << 1 | 1]); } } void update(int k, const Monoid &x){ k += sz; seg[k] = x; while(k >>= 1){ seg[k] = f(seg[k << 1], seg[k << 1 | 1]); } } Monoid query(int a, int b){ Monoid L = M1, R = M1; for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){ if(a & 1) L = f(L, seg[a++]); if(b & 1) R = f(seg[--b], R); } return f(L, R); } Monoid operator[](const int &k) const{ return seg[k + sz]; } // (type = true) : find_last // (type = false) : find_first template int find_subtree(int a, const C &check, Monoid &M, bool type){ while(a < sz){ Monoid nxt = type ? f(seg[a << 1 | type], M) : f(M, seg[a << 1 | type]); if(check(nxt)) a = a << 1 | type; else M = nxt, a = 2 * a + 1 - type; } return a - sz; } template int find_first(int a, const C &check){ Monoid L = M1; if(a <= 0){ if(check(f(L, seg[1]))) return find_subtree(1, check, L, false); return -1; } int b = sz; for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){ if(a & 1){ Monoid nxt = f(L, seg[a]); if(check(nxt)) return find_subtree(a, check, L, false); L = nxt; ++a; } } return -1; } template int find_last(int b, const C &check){ Monoid R = M1; if(b >= sz){ if(check(f(seg[1], R))) return find_subtree(1, check, R, true); return -1; } int a = sz; for(b += sz; a < b; a >>= 1, b >>= 1){ if(b & 1){ Monoid nxt = f(seg[--b], R); if(check(nxt)) return find_subtree(b, check, R, true); R = nxt; } } return -1; } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, A; cin >> N >> M >> A; vector> rights(N); for(int i = 0; i < M; ++i){ int l, r, p; cin >> l >> r >> p; rights[l - 1].emplace_back(r, p); } constexpr ll inf = 1e+17; SegmentTree seg(N + 1, [](ll a, ll b){return max(a, b);}, -inf); seg.update(0, 0LL); for(int l = 0; l < N; ++l){ ll score = seg.query(0, l) - A; if(seg[l] > score) score = seg[l]; for(auto [r, p] : rights[l]){ ll next_score = score + p + (r == N ? 0 : -A); if(next_score > seg[r]){ seg.update(r, next_score); } } } cout << seg.query(0, N + 1) << endl; return 0; }