/* -*- coding: utf-8 -*- * * 844.cc: No.844 split game - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 100000; const long long LINF = 1LL << 62; /* typedef */ typedef long long ll; typedef pair pii; typedef vector vpii; /* global variables */ vpii nbrs[MAX_N + 1]; ll dp[MAX_N + 1][2]; /* subroutines */ inline void setmax(ll &a, ll b) { if (a < b) a = b; } /* main */ int main() { int n, m, a; scanf("%d%d%d", &n, &m, &a); for (int i = 0; i < m; i++) { int l, r, p; scanf("%d%d%d", &l, &r, &p); l--; nbrs[l].push_back(pii(r, p)); } for (int i = 0; i <= n; i++) dp[i][0] = dp[i][1] = -LINF; dp[0][1] = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < 2; j++) if (dp[i][j] > -LINF) { setmax(dp[i + 1][0], dp[i][j]); setmax(dp[i + 1][1], dp[i][j] - a); } if (dp[i][1] > -LINF) { vpii &nbri = nbrs[i]; for (vpii::iterator vit = nbri.begin(); vit != nbri.end(); vit++) setmax(dp[vit->first][1], dp[i][1] + vit->second - a); } } printf("%lld\n", max(dp[n][0], dp[n][1] + a)); return 0; }