5pts求条

#include <bits/stdc++.h>
using namespace std;
int n,m;
int w[90005],l[90005],r[90005];
int dp[305][305],s[305][305][305];
int main(){
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		cin>>w[i]>>l[i]>>r[i];
		for (int k=l[i];k<=r[i];k++){
			s[l[i]][r[i]][k]=w[i];
		}
	}
	
	for (int k=1;k<=n;k++){
		for (int ls=1;ls+k-1<=n;ls++){
			int rs=ls+k-1;
			for (int d=ls;d<=rs;d++){
				s[ls][rs][d]=max(s[ls][rs][d],max(s[ls+1][rs][d],s[ls][rs-1][d]));
			}
		}
	}
	
	for (int k=1;k<=n;k++){
		for (int ls=1;ls+k-1<=n;ls++){
			int rs=ls+k-1;
			for (int d=ls;d<rs;d++){
				dp[ls][rs]=max(dp[ls][rs],dp[ls][d]+dp[d+1][rs]);
			}
			for (int d=ls;d<=rs;d++){
				dp[ls][rs]=max(dp[ls][rs],dp[ls][d-1]+dp[d+1][rs]+s[ls][rs][k]);
			}
		}
	}
	cout<<dp[1][n]<<"\n";
	return 0;
}