#include "bits/stdc++.h" using namespace std; #define int long long #define FOR(i, a, b) for(int i=(a);i<(b);i++) #define RFOR(i, a, b) for(int i=(b-1);i>=(a);i--) #define REP(i, n) for(int i=0; i<(n); i++) #define RREP(i, n) for(int i=(n-1); i>=0; i--) #define ALL(a) (a).begin(),(a).end() #define UNIQUE_SORT(l) sort(ALL(l)); l.erase(unique(ALL(l)), l.end()); #define CONTAIN(a, b) find(ALL(a), (b)) != (a).end() #define array2(type, x, y) array, x> #define vector2(type) vector > #define out(...) printf(__VA_ARGS__) int dxy[] = {0, 1, 0, -1, 0}; /*================================*/ int N, M, A; struct Range { int l; int r; int p; }; map> MAP; struct Memo { int lastPos; // 0 ~ N int score; }; signed main() { #if DEBUG std::ifstream in("input.txt"); std::cin.rdbuf(in.rdbuf()); #endif cin >> N >> M >> A; Memo dp[N+1]; REP(i, M) { Range range = *new Range(); cin >> range.l >> range.r >> range.p; range.l--; MAP[range.r].push_back(range); } dp[0].lastPos = 0; dp[0].score = 0; REP(i, N+1) { if (i > 0) dp[i] = dp[i-1]; for (auto range:MAP[i]) { int score = dp[range.l].score + range.p; if (i != N) score -= A; int lastPos = dp[range.l].lastPos; if (lastPos != range.l) { score -= A; for (auto r : MAP[range.l]) { if (lastPos == r.l) { score += r.p; } } } if (dp[i].score < score) { dp[i].score = score; dp[i].lastPos = i; } } } cout << dp[N].score << endl; return 0; }