#include #pragma GCC diagnostic ignored "-Wsign-compare" #pragma GCC diagnostic ignored "-Wsign-conversion" #define NDEBUG #define SHOW(...) static_cast(0) //!===========================================================!// //! dP dP dP !// //! 88 88 88 !// //! 88aaaaa88a .d8888b. .d8888b. .d888b88 .d8888b. 88d888b. !// //! 88 88 88ooood8 88' '88 88' '88 88ooood8 88' '88 !// //! 88 88 88. ... 88. .88 88. .88 88. ... 88 !// //! dP dP '88888P' '88888P8 '88888P8 '88888P' dP !// //!===========================================================!// template T read() { T v; return std::cin >> v, v; } template std::vector readVec(const std::size_t l) { std::vector v(l); for (auto& e : v) { std::cin >> e; } return v; } using ld = long double; using uint = unsigned int; using ll = long long; using ull = unsigned long long; constexpr unsigned int MOD = 1000000007; template constexpr T INF = std::numeric_limits::max() / 4; template constexpr F PI = static_cast(3.1415926535897932385); std::mt19937 mt{std::random_device{}()}; template bool chmin(T& a, const T& b) { return (a > b ? a = b, true : false); } template bool chmax(T& a, const T& b) { return (a < b ? a = b, true : false); } template std::vector Vec(const std::size_t n, T v) { return std::vector(n, v); } template auto Vec(const std::size_t n, Args... args) { return std::vector(n, Vec(args...)); } template constexpr T popCount(const T u) { #ifdef __has_builtin return u == 0 ? T(0) : (T)__builtin_popcountll(u); #else unsigned long long v = static_cast(u); return v = (v & 0x5555555555555555ULL) + (v >> 1 & 0x5555555555555555ULL), v = (v & 0x3333333333333333ULL) + (v >> 2 & 0x3333333333333333ULL), v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL, static_cast(v * 0x0101010101010101ULL >> 56 & 0x7f); #endif } template constexpr T log2p1(const T u) { #ifdef __has_builtin return u == 0 ? T(0) : T(64 - __builtin_clzll(u)); #else unsigned long long v = static_cast(u); return v = static_cast(v), v |= (v >> 1), v |= (v >> 2), v |= (v >> 4), v |= (v >> 8), v |= (v >> 16), v |= (v >> 32), popCount(v); #endif } template constexpr T clog(const T v) { return v == 0 ? T(0) : log2p1(v - 1); } template constexpr T msbp1(const T v) { return log2p1(v); } template constexpr T lsbp1(const T v) { #ifdef __has_builtin return __builtin_ffsll(v); #else return v == 0 ? T(0) : popCount((v & (-v)) - T(1)) + T(1); #endif } template constexpr bool ispow2(const T v) { return popCount(v) == 1; } template constexpr T ceil2(const T v) { return v == 0 ? T(1) : T(1) << log2p1(v - 1); } template constexpr T floor2(const T v) { return v == 0 ? T(0) : T(1) << (log2p1(v) - 1); } //!===================================================================!// //! .d88888b d888888P !// //! 88. "' 88 !// //! 'Y88888b. .d8888b. .d8888b. 88 88d888b. .d8888b. .d8888b. !// //! '8b 88ooood8 88' '88 88 88' '88 88ooood8 88ooood8 !// //! d8' .8P 88. ... 88. .88 88 88 88. ... 88. ... !// //! Y88888P '88888P' '8888P88 dP dP '88888P' '88888P' !// //! .88 !// //! d8888P !// //!===================================================================!// template class SegTree { public: using ValType = typename ValMonoid::ValType; SegTree(const std::size_t N, const ValType initial = ValMonoid::id()) : size(N), half(ceil2(size)), val(half << 1, ValMonoid::id()) { if (initial != ValMonoid::id()) { std::fill(val.begin() + half, val.end(), initial); for (std::size_t i = half - 1; i >= 1; i--) { up(i); } } } template SegTree(const InIt first, const InIt last) : size(std::distance(first, last)), half(ceil2(size)), val(half << 1, ValMonoid::id()) { std::copy(first, last, val.begin() + half); for (std::size_t i = half - 1; i >= 1; i--) { up(i); } } ValType get(const std::size_t a) const { return assert(a < size), val[a + half]; } void set(std::size_t a, const ValType& v) { assert(a < size); val[a += half] = v; while (a >>= 1) { up(a); } } ValType fold(std::size_t L, std::size_t R) const { assert(L < R), assert(R <= size); ValType accl = ValMonoid::id(), accr = ValMonoid::id(); for (L += half, R += half; L < R; L >>= 1, R >>= 1) { if (L & 1) { accl = acc(accl, val[L++]); } if (R & 1) { accr = acc(val[--R], accr); } } return acc(accl, accr); } friend std::ostream& operator<<(std::ostream& os, const SegTree& seg) { os << "["; for (std::size_t i = seg.half; i < seg.half + seg.size; i++) { os << seg.val[i] << (i + 1 == seg.half + seg.size ? "" : ","); } return (os << "]\n"); } private: void up(const std::size_t i) { val[i] = acc(val[i << 1], val[i << 1 | 1]); } const std::size_t size, half; std::vector val; const ValMonoid acc{}; }; //!==================================!// //! 8888ba.88ba !// //! 88 '8b '8b !// //! 88 88 88 .d8888b. dP. .dP !// //! 88 88 88 88' '88 '8bd8' !// //! dP dP dP '88888P8 dP' 'dP !// //!==================================!// template struct Max { using ValType = ElemType; ValType operator()(const ValType& a, const ValType& b) const { return std::max(a, b); } static constexpr ValType id() { return std::numeric_limits::min(); } }; int main() { const int N = read(), M = read(); const ll A = read(); std::vector L(M), R(M); std::vector P(M); for (int i = 0; i < M; i++) { std::cin >> L[i] >> R[i] >> P[i]; } std::vector ind(M); std::iota(ind.begin(), ind.end(), 0); std::sort(ind.begin(), ind.end(), [&](const int i, const int j) { return R[i] == R[j] ? L[i] < L[j] : R[i] < R[j]; }); SegTree> dp(N + 1, -INF); dp.set(0, A); for (const int i : ind) { const int l = L[i], r = R[i]; ll max = std::max(dp.get(l - 1) - A, (l == 1 ? 0 : dp.fold(0, l - 1)) - 2 * A); dp.set(r, std::max(dp.get(r), max + P[i])); } std::cout << std::max({dp.fold(0, N) - A, dp.get(N)}) << std::endl; return 0; }