P1083 70分

#include<bits/stdc++.h>
using namespace std;
long long l[1000000],r[1000000],o[1000000],p[100000];
long long l2[1000000],u[1000000];
long long a,b;
bool xuebao(int a2)
{
	memset(l2,0,sizeof(l2));
   	for(int i = 1; i <= a2; i++) 
	{
		l2[r[i]] += l[i];
       	l2[o[i]+1] -= l[i];      	
   	}   
    for(int i=1;i<=a;i++)
    {
    	u[i]=u[i-1]+l2[i];
    	if(u[i]>p[i])
    	{
    		return 0;
		}
	}
    return 1;
}
int main()
{
	cin>>a>>b;
	for(int i=1;i<=a;i++)
	{
		cin>>p[i];
	}
	for(int i=1;i<=b;i++)
	{
		cin>>l[i]>>r[i]>>o[i];
	}
	long long ll=1,rr=b,sum;
	if(xuebao(b))
	{
		cout<<"0";
		return 0;
	}
	while(ll<=rr)
	{
		long long mid=(ll+rr)/2;
		if(xuebao(mid))
		{
			ll=mid+1;
		}
		else
		{
			rr=mid-1;
			sum=mid;
		}
	}
	cout<<-1<<endl<<sum<<endl;
	return 0;
}