#include<bits/stdc++.h>

#define endl '\n'
#define pii pair<int, int>
#define int long long

using namespace std;

void solve(){
    int n,k;
    cin>>n>>k;

    vector<vector<pii>>g(n+1);

    vector<int>p(n+1);
    for(int i=1;i<=n;i++){
        cin>>p[i];
        int st=max(0ll,i-k),ed=min(n,i+k-1);
        g[st].push_back({ed,p[i]});
    }

    for(int i=1;i<=n;i++){
        g[i-1].push_back({i,0});
    }

    int que;
    cin>>que;

    for(int i=1;i<=que;i++){
        int l,r,b;
        cin>>l>>r>>b;
        g[r].push_back({l-1,-b});
    }

    deque<int>q;
    q.push_back(0);
    vector<int>vis(n+1,0),dis(n+1,-1e18),cnt(n+1,0);
    dis[0]=0;

    while(q.size()){
        int u=q.front();q.pop_front();
        vis[u]=false;

        for(auto [v,w]:g[u]){
            if(dis[v]<dis[u]+w){
                dis[v]=dis[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>n){
                    cout<<-1<<endl;
                    return;
                }
                if(!vis[v]){
                    if(!q.empty()&&dis[v]<dis[q.front()]){
                        q.push_front(v);
                    } else{
                        q.push_back(v);
                    }
                    vis[v]=1;
                }
            }
        }
    }

    cout<<dis[n]<<endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin>>t;

    while(t--){
        solve();
    }

    
    return 0;
}