#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int n, m;
int r[N]; // 每天的教室数量
int d[N], s[N], t[N]; // 订单信息

// 检查前 k 个订单是否可行
bool check(int k) {
    vector<int> diff(n + 2, 0); // 差分数组

    // 处理前 k 个订单
    for (int i = 1; i <= k; i++) {
        diff[s[i]] += d[i];
        diff[t[i] + 1] -= d[i];
    }

    // 计算每天的教室使用量
    for (int i = 1; i <= n; i++) {
        diff[i] += diff[i - 1];
        if (diff[i] > r[i]) {
            return false; // 超出可用教室数量
        }
    }

    return true;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> r[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> d[i] >> s[i] >> t[i];
    }

    // 二分查找第一个无法满足的订单
    int left = 1, right = m;
    while (left < right) {
        int mid = (left + right) / 2;
        if (check(mid)) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    // 检查是否所有订单都满足
    if (check(left)) {
        cout << 0 << endl; // 所有订单都满足
    } else {
        cout << -1 << endl; // 无法满足所有订单
        cout << left << endl; // 输出第一个无法满足的订单编号
    }

    return 0;
}

有个案例没过,还没找到问题