#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int b[110],dp[N],maxn;
vector<int>p[110];
struct node{
	int v,w;
} a[110];
int w[110],v[110],ans=0;

void solve(int now){
	int n=p[now].size(),m=b[now];
	memset(w,0,sizeof(w)),memset(v,0,sizeof(v));
	for(int j=0;j<n;j++){
		int i=p[now][j];
		w[i]=a[i].w,v[i]=a[i].v;
	}
	for(int i=1;i<=n;i++)	
		for(int j=w[i];j<m;j++)
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
	for(int i=1;i<maxn;i++) ans=max(ans,dp[i]);
}
signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie();cout.tie();
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>b[i],maxn=max(maxn,b[i]);
	for(int i=2;i<=n;i++) b[i]=min(b[i],b[i-1]);
	for(int i=1;i<=m;i++){
		int x;cin>>x;x++;
		cin>>a[i].v>>a[i].w;
		p[x].push_back(i);
	}
	for(int i=n;i>=1;i--) solve(i);
	cout<<ans;
	return 0;
}

样例他输出 $4$