题目大意：

单纯形*2。。

。

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define EPS 1e-7

#define INF 1e10

using namespace std;

int n,m;

namespace Linear_Programming{

	double A[1010][10100],b[1010],c[10100],v;

	void Pivot(int l,int e)

	{

		int i,j;

		b[l]/=A[l][e];

		for(i=1;i<=n;i++)

			if(i!=e)

				A[l][i]/=A[l][e];

		A[l][e]=1/A[l][e];

		for(i=1;i<=m;i++)

			if(i!=l&&fabs(A[i][e])>EPS)

			{

				b[i]-=A[i][e]*b[l];

				for(j=1;j<=n;j++)

					if(j!=e)

						A[i][j]-=A[i][e]*A[l][j];

				A[i][e]=-A[i][e]*A[l][e];

			}

		v+=c[e]*b[l];

		for(i=1;i<=n;i++)

			if(i!=e)

				c[i]-=c[e]*A[l][i];

		c[e]=-c[e]*A[l][e];

	}

	double Simplex()

	{

		int i,l,e;

		while(1)

		{

			for(i=1;i<=n;i++)

				if(c[i]>EPS)

					break;

			if((e=i)==n+1)

				return v;

			double temp=INF;

			for(i=1;i<=m;i++)

				if( A[i][e]>EPS && b[i]/A[i][e]<temp )

					temp=b[i]/A[i][e],l=i;

			if(temp==INF) return INF;

			Pivot(l,e);

		}

	}

}

int main()

{

	using namespace Linear_Programming;

	int i,j,x,y,z;

	cin>>m>>n;

	for(i=1;i<=m;i++)

		scanf("%lf",&b[i]);

	for(i=1;i<=n;i++)

	{

		scanf("%d%d%d",&x,&y,&z);

		for(j=x;j<=y;j++)

			A[j][i]=1;

		c[i]=z;

	}

	double ans=Simplex();

	cout<<(long long)(ans+0.5)<<endl;

	return 0;

}