#include <bits/stdc++.h>
using namespace std;
// https://space.bilibili.com/672346917

#ifndef LOCAL
#define LOG(...) 42
#endif

#define fi first
#define se second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

typedef long long LL;
typedef pair <int, int> PII;

constexpr int inf = 0x3f3f3f3f;
constexpr double EPS = 1e-8;
const double PI = acos(-1);

int multi_cases = 1;

void A_SOUL_AvA () {
    int n, radius;
    cin >> n >> radius;

    vector <array<int, 2>> adj[n + 5];
    auto add = [&](int a, int b, int c) {
        adj[a].pb({b, c});
    }; 

    vector <int> p(n + 5);
    for (int i = 1; i <= n; i++) {
        add(i - 1, i, 0);   // (i - 1) <= i + 0
        add(0, i, 0);
        cin >> p[i];
        int l = max(1, i - radius + 1);
        int r = min(n, i + radius - 1);
        // sum_r - sum_{l - 1} >= p_i
        // (l - 1) <= sum_r - p_i
        add(l - 1, r, p[i]);
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r, b;
        cin >> l >> r >> b;
        add(r, l - 1, -b);  // r <= (l - 1) + b
    }

    const int inf = 0x3f3f3f3f;
    vector <int> st(n + 1), dis(n + 1, -inf);
    vector <int> cnt(n + 1);
    auto spfa = [&]() {
        queue <int> q;
        // q.push(0);
        // dis[0] = 0;
        for (int i = 0; i <= n; i++) {
            dis[i] = 0;
            st[i] = 1;
            q.push(i);
        }

        while (q.size()) {
            int u = q.front();
            q.pop();
            st[u] = 0;
            for (auto &[v, w] : adj[u]) {
                if (dis[v] < dis[u] + w) {
                    dis[v] = dis[u] + w;
                    cnt[v] = cnt[u] + 1;
                    if (cnt[v] >= n + 1) return 1;
                    if (!st[v]) {
                        st[v] = 1;
                        q.push(v);
                    }
                }
            }
        }
        return 0;
    };

    if (spfa()) {
        cout << -1 << endl;
    } else {
        cout << dis[n] << endl;
    }
}

int main () {
    cin.tie(nullptr)->sync_with_stdio(false);
    cout << fixed << setprecision(12);

    int T = 1;
    for (multi_cases && cin >> T; T; T--) {
        A_SOUL_AvA ();
    }

    return 0;
}