#include using namespace std; typedef long long ll; #define REP(i,n) for(int (i)=0;(i)<(n);++(i)) #define FOR(i,a,b) for(int (i)=(a);(i)<(b);++(i)) #define EACH(e,v) for(auto& e:v) #define ALL(v) (v).begin(),(v).end() #define SORT(v) sort(ALL(v)) #define RSORT(v) sort((v).rbegin(),(v).rend()) #define PERM(v) SORT(v);for(bool c##p=1;c##p;c##p=next_permutation(ALL(v))) #define UNIQUE(v) SORT(v);(v).erase(unique(ALL(v)),(v).end()) template inline bool chmax(A &a,const B &b){if(a inline bool chmin(A &a,const B &b){if(a>b){a=b;return 1;}return 0;} #define int long long const int MOD = (int)1e9 + 7; const int INF = 1 << 30; const ll INFF = 1LL << 62; // 下にy, 右にx enum {R, U, L, D}; const int dx[] = {1, 0, -1, 0}; const int dy[] = {0, -1, 0, 1}; /* ・セグメント木 > build O(N) > query, update O(logN) [備考] 結合律, 単位元を持つ二項演算を, 任意の区間に関してlogNで行うデータ構造 [使用例] SegmentTree seg_sum(N, [](int a, int b){ return a+b; }, 0 ); // 区間和 SegmentTree seg_min(N, [](int a, int b){ return min(a,b); }, INF); // 区間min seg_min.set(k,x); // 要素kに値xを設定 seg_min.build(); // 上のセグメントに値を設定 seg_min.update(k,x); // 要素kを値xに変更 seg_min.add(k,x); // 要素kに値xを加算 seg_min.query(l,r); // 区間[l,r)に対する二項演算の結果を返す */ template struct SegmentTree { using F = function< T(T,T) >; vector< T > seg; int size; // データの数以上の最小の2冪, 最下段のデータの個数 const F func; const T M1; SegmentTree(int n, const F f, const T &M) : func(f), M1(M) { size = 1; while (size < n) size *= 2; seg.resize(2 * size - 1, M1); } void set(int k, T x) { seg[k + size - 1] = x; } void build() { for (int i = size - 2; i >= 0; --i) { // iの子は, (2*i+1, 2*i+2) seg[i] = func(seg[2*i+1], seg[2*i+2]); } } void update(int k, T x) { // kをseg内の添字に対応させる <- (size - 1)を足す k += size - 1; seg[k] = x; while (k > 0) { k = (k - 1) / 2; seg[k] = func(seg[2*k+1], seg[2*k+2]); } } void add(int k, T x) { // kをseg内の添字に対応させる <- (size - 1)を足す k += size - 1; seg[k] += x; while (k > 0) { k = (k - 1) / 2; seg[k] = func(seg[2*k+1], seg[2*k+2]); } } T query(int a, int b, int k = 0, int l = 0, int r = -1) { if (r < 0) r = size; if (r <= a || l >= b) return M1; if (l >= a && r <= b) return seg[k]; T f_l = query(a, b, 2*k+1, l, (l+r)/2); T f_r = query(a, b, 2*k+2, (l+r)/2, r); return func(f_l, f_r); } void debug() { for (int i = 0; i < 2 * size - 1; ++i) { cerr << seg[i] << " \n"[i==2*size-2]; } } }; int N, M, A; vector> query; signed main() { cin >> N >> M >> A; REP(i, M) { int l, r, p; cin >> l >> r >> p; query.emplace_back(make_tuple(l, r, p)); } // lについて昇順ソート SORT(query); // 区間max SegmentTree seg(2 * N, [](ll a, ll b){ return max(a,b); }, 0); REP(i, M) { int l, r, p; tie(l, r, p) = query[i]; if (l == 1) { ll pred = p - A; if (pred < 0) continue; seg.update(r, pred); } else { // l - 1 まで ll til_l_1 = p + seg.query(0, l - 1) - 2 * A; // l まで ll til_l = p + seg.query(0, l) - A; if (r == N) { til_l_1 += A; til_l += A; } ll now = seg.query(r, r + 1); chmax(now, til_l_1); chmax(now, til_l); seg.update(r, now); } } cout << seg.query(0, 2 * N) << endl; }