#include namespace DECLARATIONS { using namespace std; using ll = long long; using PI = pair; template using V = vector; using VI = V; #define _1 first #define _2 second #ifdef MY_DEBUG # define DEBUG(x) x #else # define DEBUG(x) #endif template inline void debug(T &A) { DEBUG( for (const auto &a : A) { cerr << a << " "; } cerr << '\n'; ) } template inline void debug_dim2(T &A) { DEBUG( for (const auto &as : A) { debug(as); } ) } template inline void debug(const char *format, Args const &... args) { DEBUG( fprintf(stderr, format, args ...); cerr << '\n'; ) } template string format(const std::string &fmt, Args ... args) { size_t len = std::snprintf(nullptr, 0, fmt.c_str(), args ...); std::vector buf(len + 1); std::snprintf(&buf[0], len + 1, fmt.c_str(), args ...); return std::string(&buf[0], &buf[0] + len); } } using namespace DECLARATIONS; const int MOD = 1000000007; template class SegmentTree { private: int calcN(int x) { int k = 1 << (31 - __builtin_clz(x)); return k == x ? k : k << 1; } public: int N; V dat; const T zero = (ll)-1e18; inline T f(T a, T b) { return max(a, b); } SegmentTree(int n): N(calcN(n)), dat(2 * this->N) { if (zero != 0) std::fill(dat.begin(), dat.end(), zero); } void update(int i, T a) { int ix = i + N; dat[ix] = a; while(ix > 1) { int p = ix >> 1; dat[p] = f(dat[ix], dat[ix ^ 1]); ix = p; } } /** * [a, b) */ T query(int a, int b) { T res = zero; int l = a + N, r = b - 1 + N; while(l <= r) { if ((l&1)) res = f(res, dat[l]); if (!(r&1)) res = f(res, dat[r]); l = (l + 1) >> 1; // 右の子供なら右の親に移動 r = (r - 1) >> 1; // 左の子供なら左の親に移動 } return res; } }; int main() { std::ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, A; cin >> N >> M >> A; V> S(M); for (int i = 0; i < M; ++i) { int l, r, p; cin >> l >> r >> p; S[i] = {PI(r, l-1), p}; // rで降順 } sort(S.begin(), S.end()); SegmentTree t(N + 1); t.update(0, 0); for (int i = 0; i < M; ++i) { // (r, l)なのに注意 int l = S[i]._1._2; int r = S[i]._1._1; int p = S[i]._2; ll v = max(t.query(l, l + 1) - A, t.query(0, l) - 2 * A) + p; debug("l:%d r:%d p:%d v:%d", l, r, p, v); if (r == N) v += A; // Nはただで線を引ける if (t.query(r, r + 1) < v) t.update(r, v); } ll ans = t.query(0, N + 1); cout << ans; return 0; }