#include<iostream>
#define ll long long
using namespace std;
ll r[1000010];
ll d[1000010],s[1000010],t[1000010];
ll nw[1000010];
ll n,m;
bool check(ll x){
  for(ll i = 1;i <= n;i++)nw[i] = 0; //将nw数组归零
  //差分
  for(ll i = 1;i <= x;i++)nw[s[i]] += d[i],nw[t[i]+i] -= d[i];
  ll us = 0;
  for(ll i = 1;i <= n;i++){
    us += nw[i];
    //检查会不会不够教室
    if(us > r[i])return 0;
  }
  return 1;
}
signed main(){
  cin >> n >> m;
  for(ll i = 1;i <= n;i++)cin >> r[i];
  for(ll i = 1;i <= m;i++){
    cin >> d[i] >> s[i] >> t[i];
  }
  ll l = 0,r = m;
  if(check(m)){ //直接检查，如果没有问题直接输出0
    cout << 0;
    return 0;
  }
  while(l < r){ //二分寻找不满足条件的订单
    ll mid = (l + r)/2;
    if(check(mid)){
      l = mid + 1;
    }else{
      r = mid;
    }
  }
  cout << -1 << endl << l; //输出结果
  return 0;
}