#include #include #include #include typedef int32_t i32; typedef int64_t i64; #define MAX(a,b) ((a)>(b)?(a):(b)) #define ALLOC(size,type) ((type*)calloc((size),sizeof(type))) #define SORT(a,num,cmp) qsort((a),(num),sizeof(*(a)),cmp) typedef struct range { i32 l, r, p; } range; int cmp_range (const void *a, const void *b) { i32 d = ((range *)a)->r - ((range *)b)->r; return d == 0 ? 0 : d < 0 ? -1 : 1; } void run (void) { i32 n, m, a; scanf ("%" SCNi32 "%" SCNi32 "%" SCNi32, &n, &m, &a); range *q = ALLOC (m, range); for (i32 i = 0; i < m; ++i) { i32 l, r, p; scanf ("%" SCNi32 "%" SCNi32 "%" SCNi32, &l, &r, &p); l--; q[i] = (range) {l, r, p}; } SORT (q, m, cmp_range); i64 *dp = ALLOC (n + 1, i64); for (i32 i = 0, j = 0; i <= n; ++i) { i64 cost = 0 < i && i < n ? -a : 0; i64 max = cost; for (; j < m && q[j].r == i; ++j) { max = MAX (max, cost + q[j].p + dp[q[j].l]); } dp[i] = max; } i64 ans = 0; for (i32 i = 0; i <= n; ++i) { ans = MAX (ans, dp[i]); } printf ("%" PRIi64 "\n", ans); } int main (void) { run(); return 0; }