#include #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; using lint=long long; template struct interval{ T l,r; int wt; interval(){} interval(const T& l,const T& r,int wt):l(l),r(r),wt(wt){} bool operator<(const interval& I)const{ return make_tuple(r,l)> I(m); rep(i,m) scanf("%d%d%d",&I[i].l,&I[i].r,&I[i].wt), I[i].r++; vector X={0,1,L+1}; rep(i,m){ X.emplace_back(I[i].l); X.emplace_back(I[i].r); } sort(X.begin(),X.end()); X.erase(unique(X.begin(),X.end()),X.end()); rep(i,m){ I[i].l=lower_bound(X.begin(),X.end(),I[i].l)-X.begin(); I[i].r=lower_bound(X.begin(),X.end(),I[i].r)-X.begin(); } sort(I.begin(),I.end()); int n=X.size(),idx=0; // dp[i] = ([1, X[i]) に含まれる区間だけを考えて, X[i] の左に区切りを入れたときのスコアの最大値) vector dp(n,-INF),dp_max(n,-INF); dp[1]=0; dp_max[1]=0; for(int i=2;i