#include using namespace std; using Int = long long; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a>n>>m>>a; vector ls(m),rs(m),ps(m); for(Int i=0;i>ls[i]>>rs[i]>>ps[i],ls[i]--; vector > G(n+1); for(Int i=0;i dp1(n+1,-INF); vector dp2(n+1,-INF); dp1[0]=dp2[0]=0; Int ans=0; for(Int i=1;i<=n;i++){ chmax(dp2[i],dp2[i-1]); Int b=i==n?a:0; for(Int k:G[i]){ chmax(dp1[i],dp1[ls[k]]+ps[k]-a+b); chmax(dp1[i],dp2[ls[k]]+ps[k]-a*2+b); } chmax(dp2[i],dp1[i]); chmax(ans,dp2[i]); } cout<