#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

int a[1005];
int s[10005];
int t[10005];
int c[10005];
int n, m;
int cnt[1005];
int ans = 1e9;

bool check()
{
	int tt[15] = {0};
	for (int i = 1; i <= m; i++)
	{
		for (int j = s[i]; j <= t[i]; j++)
		{
			tt[j] += cnt[i];
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (tt[i] < a[i]) return false;
	}
	return true;
	
}

void dfs(int step, int cost)
{
	if (cost >= ans) return ;
	if (step > m)
	{
		if (check())
		{
			ans = min(ans, cost);
		}
		return ;
	}
	for (int i = 0; i <= 10; i++)
	{
		cnt[step] = i;
		dfs(step + 1, cost + c[step] * i);
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	for (int i = 1; i <= m; i++)
	{
		cin >> s[i] >> t[i] >> c[i];
	}
	dfs(1, 0);
	cout << ans << endl;
	return 0;
}

要怎么优化啊