#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=10001,maxq=100,maxe=maxn+maxn+maxq;

int te,n,K,Q,a[maxn+5],sum;
int E,lnk[maxn+5],nxt[maxe+5],to[maxe+5],w[maxe+5];
LL dis[maxn+5];int que[maxn+5],cnt[maxn+5];bool vis[maxn+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
	static char buf[100000],*l=buf,*r=buf;
	return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
	T tot=0;char ch=readc(),lst='+';
	while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
	while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
	lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
inline void Add(int x,int y,int z) {to[++E]=y;w[E]=z;nxt[E]=lnk[x];lnk[x]=E;}
#define AMOD(x) ((x)+1<maxn?(x)+1:0)
LL Spfa(int S,int T){
	for (int i=0;i<=n;i++) dis[i]=1e18,cnt[i]=0,vis[i]=false;
	int Head=0,Tail=0;
	dis[S]=0;que[++Tail]=S;vis[S]=true;
	while (Head!=Tail){
		int x=que[Head=AMOD(Head)];vis[x]=false;
		if ((++cnt[x])>n) return -1;
		for (int j=lnk[x],u;j;j=nxt[j])
			if (dis[x]+w[j]<dis[u=to[j]]){
				dis[u]=dis[x]+w[j];
				if (!vis[u]) que[Tail=AMOD(Tail)]=u,vis[u]=true;
			}
	}
	return -dis[T];
}
int main(){
	for (readi(te);te;te--){
		readi(n);readi(K);sum=0;
		for (int i=1;i<=n;i++) readi(a[i]),sum+=a[i];
		E=0;for (int i=0;i<=n;i++) lnk[i]=0;
		for (int i=1;i<=n;i++) Add(i,i-1,0);
		for (int i=1;i<=n;i++){
			int L=max(i-K+1,1),R=min(i+K-1,n);
			Add(R,L-1,-a[i]);
		}
		for (readi(Q);Q;Q--){
			int L,R,B;readi(L);readi(R);readi(B);
			Add(L-1,R,B);
		}
//		int L=0,R=sum;
//		for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)){
//			int temlnk=lnk[0];
//			Add(0,n,mid);
//			Spfa(n,0)<1e18?R=mid-1:L=mid+1;
//			lnk[0]=temlnk;E--;
//		}
		printf("%lld\n",Spfa(n,0));
	}
	return 0;
}