#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
const int N = 1e4 + 10;
int d[N], vis[N], cnt[N], S, n, k;
vector<pair<int, int>> g[N];

bool spfa()
{
	_for(i, 0, n + 1) d[i] = -1e9, vis[i] = cnt[i] = 0;
	d[S] = 0;
	deque<int> q;
	q.push_back(S);

	while(!q.empty())
	{
		int u = q.front(); q.pop_front();
		//printf("u: %d\n", u);
		vis[u] = 0;
		for(auto [v, w]: g[u])
			if(d[v] < d[u] + w)   //注意这里是最长路
			{
				d[v] = d[u] + w;
				if(!vis[v])
				{
					if(!q.empty() && d[v] > d[q.front()]) q.push_front(v);  //注意判空
					else q.push_back(v);
					vis[v] = 1;
					if(++cnt[v] > n) return false;
				}
			}
	}
	return true;
}

int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		scanf("%d%d", &n, &k);
		_for(i, 0, n + 1) g[i].clear();
		S = n + 1;
		_for(i, 1, n)
		{
			int p; scanf("%d", &p);
			g[max(i - k, 0)].push_back({min(i + k - 1, n), p});
			g[i - 1].push_back({i, 0});
		}
		_for(i, 0, n) g[S].push_back({i, 0});

		int q; scanf("%d", &q);
		_for(i, 1, q)
		{
			int l, r, b;
			scanf("%d%d%d", &l, &r, &b);
			g[r].push_back({l - 1, -b});
		}

		if(!spfa()) puts("-1");
		else printf("%d\n", d[n]);
	} 
	
	return 0;
}