// IO #include #include #include #include // algorithm #include #include #include // container #include #include #include #include #include #include #include #include #include // others #include #include #include #include #include // type alias using lint = long long; using ldouble = long double; template using greater_priority_queue = std::priority_queue, std::greater>; /* ----- class ----- */ template struct Edge { int src, dst; Cost cost; Edge(int src = -1, int dst = -1, Cost cost = 1) : src(src), dst(dst), cost(cost){}; bool operator<(const Edge& e) const { return this->cost < e.cost; } bool operator>(const Edge& e) const { return this->cost > e.cost; } }; template using Edges = std::vector>; template using Graph = std::vector>>; /* ----- debug ----- */ #if __has_include("../setting/source/debug.hpp") #include "../setting/source/debug.hpp" #endif /* ----- short functions ----- */ template inline T sq(T a) { return a * a; } template inline T iceil(T n, T d) { return (n + d - 1) / d; } template T gcd(T a, T b) { while (b > 0) { a %= b; std::swap(a, b); } return a; } template T ipow(T b, U n) { T ret = 1; while (n > 0) { if (n & 1) ret *= b; n >>= 1; b *= b; } return ret; } // 0-indexed template inline T kthbit(T a, U k) { return (a >> k) & 1; } template inline T mask(T a, U k) { return a & ((1 << k) - 1); } template std::map compress(std::vector& v) { std::sort(v.begin(), v.end()); v.erase(std::unique(v.begin(), v.end()), v.end()); std::map rev; for (int i = 0; i < v.size(); ++i) rev[v[i]] = i; return rev; } template T Vec(T v) { return v; } template auto Vec(size_t l, Ts... ts) { return std::vector(ts...))>(l, Vec(ts...)); } /* ----- constants ----- */ // const int INF = std::numeric_limits::max() / 3; const lint INF = std::numeric_limits::max() / 3; // const ldouble PI = acos(-1); // const ldouble EPS = 1e-10; // std::mt19937 mt(int(std::time(nullptr))); using namespace std; struct Seg { int l, r; lint p; Seg(int l = 0, int r = 0, lint p = 0) : l(l), r(r), p(p) {} bool operator<(const Seg& a) const { return l == a.l ? r < a.r : l < a.l; } }; int main() { int N, M, A; cin >> N >> M >> A; vector segs(M); for (auto& s : segs) { cin >> s.l >> s.r >> s.p; } sort(segs.begin(), segs.end()); auto dp = Vec(M + 1, 2, 0LL); dp[0][0] = -INF; // dp[i][b] = [0, i)まで見て、 // segs[i].lの左に線が引かれて[いる/いない]ときの最適解 for (int i = 0; i < M; ++i) { // iを使わない場合 dp[i + 1][0] = max({dp[i + 1][0], dp[i][0], dp[i][1]}); // iを使う場合 // segs[i]とsegs[j]が交わらない最小のjを求める int j = lower_bound(segs.begin(), segs.end(), Seg(segs[i].r + 1, -1)) - segs.begin(); int cost = A * 2; if (segs[i].r == N) cost -= A; bool b = (segs[j].l == segs[i].r + 1); dp[j][b] = max({dp[j][b], dp[i][0] + segs[i].p - cost, dp[i][1] + segs[i].p - (cost - A)}); } cout << max(dp[M][0], dp[M][1]) << endl; return 0; }