Cod sursă (job #769215)

// Problem: Killing Zombies
// Contest: CodeChef - COLE2018
// URL: https://www.codechef.com/problems/CLKLZM
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

/*
⣿⣿⣿⣿⣿⣿⡷⣯⢿⣿⣷⣻⢯⣿⡽⣻⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣇⠸⣿⣿⣆⠹⣿⣿⢾⣟⣯⣿⣿⣿⣿⣿⣿⣽⣻⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣻⣽⡿⣿⣎⠙⣿⣞⣷⡌⢻⣟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⣿⣿⣿⣿⣿⡄⠹⣿⣿⡆⠻⣿⣟⣯⡿⣽⡿⣿⣿⣿⣿⣽⡷⣯⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣟⣷⣿⣿⣿⡀⠹⣟⣾⣟⣆⠹⣯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⢠⡘⣿⣿⡄⠉⢿⣿⣽⡷⣿⣻⣿⣿⣿⣿⡝⣷⣯⢿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣯⢿⣾⢿⣿⡄⢄⠘⢿⣞⡿⣧⡈⢷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⢸⣧⠘⣿⣷⠈⣦⠙⢿⣽⣷⣻⣽⣿⣿⣿⣿⣌⢿⣯⢿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣟⣯⣿⢿⣿⡆⢸⡷⡈⢻⡽⣷⡷⡄⠻⣽⣿⣿⡿⣿⣿⣿⣿⣿⣿⣷⣿⣿⣿⣿⣏⢰⣯⢷⠈⣿⡆⢹⢷⡌⠻⡾⢋⣱⣯⣿⣿⣿⣿⡆⢻⡿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⡎⣿⢾⡿⣿⡆⢸⣽⢻⣄⠹⣷⣟⣿⣄⠹⣟⣿⣿⣟⣿⣿⣿⣿⣿⣿⣽⣿⣿⣿⡇⢸⣯⣟⣧⠘⣷⠈⡯⠛⢀⡐⢾⣟⣷⣻⣿⣿⣿⡿⡌⢿⣻⣿⣿
⣿⣿⣿⣿⣿⣿⣧⢸⡿⣟⣿⡇⢸⣯⣟⣮⢧⡈⢿⣞⡿⣦⠘⠏⣹⣿⣽⢿⣿⣿⣿⣿⣯⣿⣿⣿⡇⢸⣿⣿⣾⡆⠹⢀⣠⣾⣟⣷⡈⢿⣞⣯⢿⣿⣿⣿⢷⠘⣯⣿⣿
⣿⣿⣿⣿⣿⣿⣿⡈⣿⢿⣽⡇⠘⠛⠛⠛⠓⠓⠈⠛⠛⠟⠇⢀⢿⣻⣿⣯⢿⣿⣿⣿⣷⢿⣿⣿⠁⣾⣿⣿⣿⣧⡄⠇⣹⣿⣾⣯⣿⡄⠻⣽⣯⢿⣻⣿⣿⡇⢹⣾⣿
⣿⣿⣿⣿⣿⣿⣿⡇⢹⣿⡽⡇⢸⣿⣿⣿⣿⣿⣞⣆⠰⣶⣶⡄⢀⢻⡿⣯⣿⡽⣿⣿⣿⢯⣟⡿⢀⣿⣿⣿⣿⣿⣧⠐⣸⣿⣿⣷⣿⣿⣆⠹⣯⣿⣻⣿⣿⣿⢀⣿⢿
⣿⣿⣿⣿⣿⣿⣿⣿⠘⣯⡿⡇⢸⣿⣿⣿⣿⣿⣿⣿⣧⡈⢿⣳⠘⡄⠻⣿⢾⣽⣟⡿⣿⢯⣿⡇⢸⣿⣿⣿⣿⣿⣿⡀⢾⣿⣿⣿⣿⣿⣿⣆⠹⣾⣷⣻⣿⡿⡇⢸⣿
⣿⣿⣿⣿⣿⣿⣿⣿⡇⢹⣿⠇⢸⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⠻⡇⢹⣆⠹⣟⣾⣽⣻⣟⣿⣽⠁⣾⣿⣿⣿⣿⣿⣿⣇⣿⣿⠿⠛⠛⠉⠙⠋⢀⠁⢘⣯⣿⣿⣧⠘⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⡈⣿⡃⢼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡙⠌⣿⣆⠘⣿⣞⡿⣞⡿⡞⢠⣿⣿⣿⣿⣿⡿⠛⠉⠁⢀⣀⣠⣤⣤⣶⣶⣶⡆⢻⣽⣞⡿⣷⠈⣿
⣿⣿⣿⣿⣿⣿⣿⣿⡿⠃⠘⠁⠉⠉⠉⠉⠉⠉⠉⠉⠉⠙⠛⠛⢿⣄⢻⣿⣧⠘⢯⣟⡿⣽⠁⣾⣿⣿⣿⣿⣿⡃⢀⢀⠘⠛⠿⢿⣻⣟⣯⣽⣻⣵⡀⢿⣯⣟⣿⢀⣿
⣿⣿⣿⣟⣿⣿⣿⣿⣶⣶⡆⢀⣿⣾⣿⣾⣷⣿⣶⠿⠚⠉⢀⢀⣤⣿⣷⣿⣿⣷⡈⢿⣻⢃⣼⣿⣿⣿⣿⣻⣿⣿⣿⡶⣦⣤⣄⣀⡀⠉⠛⠛⠷⣯⣳⠈⣾⡽⣾⢀⣿
⣿⢿⣿⣿⣻⣿⣿⣿⣿⣿⡿⠐⣿⣿⣿⣿⠿⠋⠁⢀⢀⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣌⣥⣾⡿⣿⣿⣷⣿⣿⢿⣷⣿⣿⣟⣾⣽⣳⢯⣟⣶⣦⣤⡾⣟⣦⠘⣿⢾⡁⢺
⣿⣻⣿⣿⡷⣿⣿⣿⣿⣿⡗⣦⠸⡿⠋⠁⢀⢀⣠⣴⢿⣿⣽⣻⢽⣾⣟⣷⣿⣟⣿⣿⣿⣳⠿⣵⣧⣼⣿⣿⣿⣿⣿⣾⣿⣿⣿⣿⣿⣽⣳⣯⣿⣿⣿⣽⢀⢷⣻⠄⠘
⣿⢷⣻⣿⣿⣷⣻⣿⣿⣿⡷⠛⣁⢀⣀⣤⣶⣿⣛⡿⣿⣮⣽⡻⣿⣮⣽⣻⢯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⢀⢸⣿⢀⡆
⠸⣟⣯⣿⣿⣷⢿⣽⣿⣿⣷⣿⣷⣆⠹⣿⣶⣯⠿⣿⣶⣟⣻⢿⣷⣽⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢀⣯⣟⢀⡇
⣇⠹⣟⣾⣻⣿⣿⢾⡽⣿⣿⣿⣿⣿⣆⢹⣶⣿⣻⣷⣯⣟⣿⣿⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢀⡿⡇⢸⡇
⣿⣆⠹⣷⡻⣽⣿⣯⢿⣽⣻⣿⣿⣿⣿⣆⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠛⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⢸⣿⠇⣼⡇
⡙⠾⣆⠹⣿⣦⠛⣿⢯⣷⢿⡽⣿⣿⣿⣿⣆⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⠎⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠏⢀⣿⣾⣣⡿⡇
⣿⣷⡌⢦⠙⣿⣿⣌⠻⣽⢯⣿⣽⣻⣿⣿⣿⣧⠩⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⢰⢣⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠃⢀⢀⢿⣞⣷⢿⡇
⣿⣽⣆⠹⣧⠘⣿⣿⡷⣌⠙⢷⣯⡷⣟⣿⣿⣿⣷⡀⡹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣈⠃⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⢀⣴⡧⢀⠸⣿⡽⣿⢀
⢻⣽⣿⡄⢻⣷⡈⢿⣿⣿⢧⢀⠙⢿⣻⡾⣽⣻⣿⣿⣄⠌⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠛⢁⣰⣾⣟⡿⢀⡄⢿⣟⣿⢀
⡄⢿⣿⣷⢀⠹⣟⣆⠻⣿⣿⣆⢀⣀⠉⠻⣿⡽⣯⣿⣿⣷⣈⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⢀⣠⠘⣯⣷⣿⡟⢀⢆⠸⣿⡟⢸
⣷⡈⢿⣿⣇⢱⡘⢿⣷⣬⣙⠿⣧⠘⣆⢀⠈⠻⣷⣟⣾⢿⣿⣆⠹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⣠⡞⢡⣿⢀⣿⣿⣿⠇⡄⢸⡄⢻⡇⣼
⣿⣷⡈⢿⣿⡆⢣⡀⠙⢾⣟⣿⣿⣷⡈⠂⠘⣦⡈⠿⣯⣿⢾⣿⣆⠙⠻⠿⠿⠿⠿⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠛⢋⣠⣾⡟⢠⣿⣿⢀⣿⣿⡟⢠⣿⢈⣧⠘⢠⣿
⣿⣿⣿⣄⠻⣿⡄⢳⡄⢆⡙⠾⣽⣿⣿⣆⡀⢹⡷⣄⠙⢿⣿⡾⣿⣆⢀⡀⢀⢀⢀⢀⢀⢀⢀⢀⢀⢀⢀⢀⣀⣠⣴⡿⣯⠏⣠⣿⣿⡏⢸⣿⡿⢁⣿⣿⢀⣿⠆⢸⣿
⣿⣿⣿⣿⣦⡙⣿⣆⢻⡌⢿⣶⢤⣉⣙⣿⣷⡀⠙⠽⠷⠄⠹⣿⣟⣿⣆⢙⣋⣤⣤⣤⣄⣀⢀⢀⢀⢀⣾⣿⣟⡷⣯⡿⢃⣼⣿⣿⣿⠇⣼⡟⣡⣿⣿⣿⢀⡿⢠⠈⣿
⣿⣿⣿⣿⣿⣷⣮⣿⣿⣿⡌⠁⢤⣤⣤⣤⣬⣭⣴⣶⣶⣶⣆⠈⢻⣿⣿⣆⢻⣿⣿⣿⣿⣿⣿⣷⣶⣤⣌⣉⡘⠛⠻⠶⣿⣿⣿⣿⡟⣰⣫⣴⣿⣿⣿⣿⠄⣷⣿⣿⣿
*/

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

typedef long long ll;
typedef long double ld;
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define pp pop_back
#define mp make_pair
ll MOD = 998244353;
const ld PI = 3.141592653589793238460;
const ll INF = 1e9 + 7;

#define CHAR_RANGE 128

const ll N = 3e5;

ll sieve[N + 1];

void SieveOfEratosthenes() {
    memset(sieve, 0, sizeof(sieve));
    for(ll x = 2; x <= N; x++) {
        if(sieve[x]) continue;
        for(ll u = 2*x; u <= N; u += x) {
            sieve[u] = x;
        }
    }
}

ll pow_(ll a, ll b) {
    //a %= INF;
    ll res = 1;
    while(b > 0) {
        if(b & 1) res = (res * a);// % INF;
        a = (a * a);// % INF;
        b >>= 1;
    }
    return res;
}

ll gcd(ll a, ll b) {
    if(b == 0) return a;
    return gcd(b, a % b);
}

ll lcm(ll x, ll y) {
    return (x * y) / gcd(x,y);
}

bool isPrime(ll n) {
    if(n < 2) return false;
    for(ll i = 2; (i * i) <= n; i++) {
        if(n % i == 0) return false;
    }
    return true;
}

int get_bit_count(ll x) {
    return __builtin_popcountll(x);
}

ll extended_euclid(ll a, ll b, ll &x, ll &y) {
    if(b == 0) {
        x = 1; y = 0;
        return a;
    }
    ll x1, y1;
    ll d = extended_euclid(b, a % b, x1, y1);
    x = y1;
    y = x1 - (y1 * (a / b));
    return d;
}

ll modular_inverse(ll a, ll m) {
    ll x,y;
    ll g = extended_euclid(a, m, x, y);
    if(g != 1) return -1;
    x = ((x % m) + m) % m;
    return x;
}

const ll max_size = 2e5 + 5;
vector<ll> adj[max_size];
//vector<pair<ll, ll>> adj[max_size];
//set<ll> adj[max_size];
int visited[max_size];
//int visited[max_size][max_size];
//int par[max_size];
//vector<vector<int>> grid, visited;
//vector<string> g;
//vector<pair<int, int>> v;
//int n,m;
//int x,y, d_x, d_y;
//string str;
//int des_x, des_y;
//char grid[max_size][max_size];
int dz[] = {0, 0, 0 ,0, 1, -1};
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
//map<pair<ll, ll>, ll> edges;

// vector<int> tree_traversal;
// int node_id[max_size], subtree[max_size], value[max_size];


// fenwickTree .......................................................start
/*
ll n;

vector<ll> table;

void update(ll i, ll delta) {
    while(i < (n + 1)) {
        table[i] += delta;
        i += (i & (-i));
    }
}

ll rangeSum(ll i) {
    ll sum = 0;
    while(i > 0) {
        sum += table[i];
        i -= (i & (-i));
    }
    return sum;
}

void initialise() {
    table.clear();
    table.resize(n + 1, 0);
}

// end.........................................................fenwickTree*/


// segmentTree .......................................................start

/*
ll n;
vector<ll> lo, hi, minm, maxm, delta, v;

void prop(ll i) {                    // lazy propagation
    delta[2*i] += delta[i];
    delta[2*i + 1] += delta[i];
    delta[i] = 0;
}

void update(ll i) {
    minm[i] = min(minm[2*i] + delta[2*i], minm[2*i + 1] + delta[2*i + 1]);
    maxm[i] = max(maxm[2*i] + delta[2*i], maxm[2*i + 1] + delta[2*i + 1]);
}

void increment(ll i, ll a, ll b, ll val) {
    // no cover case
    if(b < lo[i] || a > hi[i]) return;

    // complete cover case
    if(a <= lo[i] && hi[i] <= b) {
        delta[i] += val;
        return;
    }

    // partial cover case
    prop(i);
    increment(2*i, a, b, val);
    increment(2*i + 1, a, b, val);
    update(i);
}

ll minimum(ll i, ll a, ll b) {
    // no cover case
    if(b < lo[i] || a > hi[i]) return INF;

    // complete cover case
    if(a <= lo[i] && hi[i] <= b) {
        return minm[i] + delta[i];
    }

    // partial cover case
    prop(i);
    ll minLeft = minimum(2*i, a, b);
    ll minRight = minimum(2*i + 1, a, b);
    update(i);

    return min(minLeft, minRight);
}

ll maximum(ll i, ll a, ll b) {
    // no cover case
    if(b < lo[i] || a > hi[i]) return -1;

    // complete cover case
    if(a <= lo[i] && hi[i] <= b) {
        return maxm[i] + delta[i];
    }

    // partial cover case
    prop(i);
    ll maxLeft = maximum(2*i, a, b);
    ll maxRight = maximum(2*i + 1, a, b);
    update(i);

    return max(maxLeft, maxRight);
}

void init(ll i, ll a, ll b) {
    lo[i] = a;
    hi[i] = b;
    if(a == b) {
        minm[i] = v[a];
        maxm[i] = v[a];
        return;
    }
    ll mid = a + (b - a) / 2;
    init(2*i, a, mid);
    init(2*i + 1, mid + 1, b);
    update(i);
}

void initialise() {
    lo.clear();
    lo.resize(4*n + 1);
    hi.clear();
    hi.resize(4*n + 1);
    minm.clear();
    minm.resize(4*n + 1);
    maxm.clear();
    maxm.resize(4*n + 1);
    delta.clear();
    delta.resize(4*n + 1, 0);
    init(1, 0, n - 1);
}


// end.................................................... segmentTree*/ 

bool cmp(pair<int, int> &a, pair<int, int> &b) {
    return a.ff > b.ff;
}

// bool check(int x, int y) {
//     if(x < 0 || x >= (n - 1) || y < 0 || y >= (n - 1)) return false;
//     return true;
// }

/*
string binary_rep(ll x) {
    string s = "";
    while(x) {
        s += ('0' + (x % 2));
        x /= 2;
    }
    reverse(s.begin(), s.end());
    return s;
}

ll dec_rep(string str) {
    reverse(str.begin(), str.end());
    ll power = 1;
    ll ans = 0;
    for(auto val : str) {
        ans += (power*(val - '0'));
        power *= 2;
    }
    return ans;
}
*/

void solve() {
    ll n,m; in>>n>>m;
    ll zombies[n];
    for(ll i = 0; i < n; i++) {
        in>>zombies[i];
    }
    vector<pair<ll, ll>> beams[n];
    for(ll i = 0; i < m; i++) {
        ll l,r,k; in>>l>>r>>k;
        l--; r--;
        beams[l].pb({r, k});
    }
    set<pair<ll, ll>> s;
    ll sum = 0, ans = 0;
    ll dif_arr[n];
    memset(dif_arr, 0, sizeof(dif_arr));
    for(ll i = 0; i < n; i++) {
        for(auto p : beams[i]) {
            s.insert(p);
        }
        sum -= dif_arr[i];
        zombies[i] -= sum;
        while(zombies[i] > 0) {
            if(s.empty() || s.rbegin()->ff < i) {
                ans = -1;
                break;
            }
            ll r,k;
            tie(r, k) = *s.rbegin();
            s.erase({r, k});
            ll x = min(zombies[i], k);
            ans += x;
            zombies[i] -= x; k -= x;
            if(r + 1 < n) dif_arr[r + 1] += x;
            sum += x;
            if(k) s.insert({r, k});
        }
        if(ans == -1) break;
    }
        out<<ans<<"\n";
}
ifstream in;
ofstream out;
int main() {
    ios_base::sync_with_stdio(0);
    in.tie(0); out.tie(0);
    in.open("stampile.in");
    out.open("stampile.out");
    //compute();
    //SieveOfEratosthenes();
    int t = 1;
    in>>t;
    solve();
    return 0;
}
/*
Notes : 
 (a * b) % m = ((a % m) * (b % m)) % m
 (a * b * c) % m = ((a % m) * (b % m) * (c % m)) % m
 The same property holds for more than three numbers

 Let A and B be positive integers, and g be the greatest common divisor of A and B. Let
 A = ag and B = bg; then a integers 0, B mod A, 2B mod A, 3B mod A... (a - 1)B mod A contains
 each of 0,g,2g,....(a - 1)g (that is, all multiples of g between 0 and A - 1, inclusive) exactly once.
*/
/*
  ASCII value :
  {a, z} = {97, 122}
  {A, Z} = {65, 90}

  Convert string to char array :
  std::string s = "GeeksForGeeks";
  char* char_arr = &s[0];

  strtok function : char *strtok(char *s1, const char *s2);
  in.get() == 10 // for checking no input exist further in the line
  ctrl + shift + D : to duplicate a line
*/