#include<bits/stdc++.h>
using namespace std;
//MasterChef
const int MAX = 1e6+7;
 
int n,m,k;
void update(int l,int r,int b,int e,int node,int val,vector<int> &tree){
    if(l==r){
      tree[node] = min(tree[node],val);
    }
 
    if(b>r || e<r) return;
    int m = (l+r)/2;
    update(l,r,b,m,2*node+1,val,tree);
    update(l,r,m+1,r,2*node+2,val,tree);
}
 
int query(int b,int e,int l,int r,int node,vector<int> &tree){
 
    if(b>r || e<l) return INT_MAX;
    if(b>=l && e<=r) return tree[node];
    if(l==r) return tree[node];
    int m = (l+r)/2;
    return min(query(b,m,l,r,2*node+1,tree),query(m+1,e,l,r,2*node+2,tree));
}
 
int solve(int k,int i,vector<vector<int> > &dp,vector<int> &a, vector<int> & tree){
 
  if(dp[i][k]!=-1) return dp[i][k];
  if(k<0) return INT_MIN;
  if(i==n) return 0;
  int mn = 0;
  if(a[i]>=0) mn = a[i] + solve(i+1,k,dp,a,tree);
  else mn = max(a[i] + solve(i+1,k,dp,a,tree),solve(i+1,k - query(0,n-1,i,i,0,tree),dp,a,tree));
  dp[i][k] = mn;
  return mn;
}
 
 
int main(){
 
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
 
  int t; cin>>t;
  while(t-->0)
  {
    cin>>n>>k>>m;
    vector<int> tree(5*n,INT_MAX),a(n);
 
    vector<vector<int> > dp(n,vector<int>(k,-1));
    for(int i=0;i<n;i++) cin>>a[i];
 
    for(int i=1;i<=m;i++){
      int l,r,c;
      cin>>l>>r>>c;
      update(l,r,0,n-1,0,c,tree);
    }
 
    cout<<solve(k,0,dp,a,tree)<<'\n';
}
 
  return 0;
}
 

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKLy9NYXN0ZXJDaGVmCmNvbnN0IGludCBNQVggPSAxZTYrNzsKCmludCBuLG0sazsKdm9pZCB1cGRhdGUoaW50IGwsaW50IHIsaW50IGIsaW50IGUsaW50IG5vZGUsaW50IHZhbCx2ZWN0b3I8aW50PiAmdHJlZSl7CiAgICBpZihsPT1yKXsKICAgICAgdHJlZVtub2RlXSA9IG1pbih0cmVlW25vZGVdLHZhbCk7CiAgICB9CiAgICAKICAgIGlmKGI+ciB8fCBlPHIpIHJldHVybjsKICAgIGludCBtID0gKGwrcikvMjsKICAgIHVwZGF0ZShsLHIsYixtLDIqbm9kZSsxLHZhbCx0cmVlKTsKICAgIHVwZGF0ZShsLHIsbSsxLHIsMipub2RlKzIsdmFsLHRyZWUpOwp9CgppbnQgcXVlcnkoaW50IGIsaW50IGUsaW50IGwsaW50IHIsaW50IG5vZGUsdmVjdG9yPGludD4gJnRyZWUpewoKICAgIGlmKGI+ciB8fCBlPGwpIHJldHVybiBJTlRfTUFYOwogICAgaWYoYj49bCAmJiBlPD1yKSByZXR1cm4gdHJlZVtub2RlXTsKICAgIGlmKGw9PXIpIHJldHVybiB0cmVlW25vZGVdOwogICAgaW50IG0gPSAobCtyKS8yOwogICAgcmV0dXJuIG1pbihxdWVyeShiLG0sbCxyLDIqbm9kZSsxLHRyZWUpLHF1ZXJ5KG0rMSxlLGwsciwyKm5vZGUrMix0cmVlKSk7Cn0KCmludCBzb2x2ZShpbnQgayxpbnQgaSx2ZWN0b3I8dmVjdG9yPGludD4gPiAmZHAsdmVjdG9yPGludD4gJmEsIHZlY3RvcjxpbnQ+ICYgdHJlZSl7CiAgCiAgaWYoZHBbaV1ba10hPS0xKSByZXR1cm4gZHBbaV1ba107CiAgaWYoazwwKSByZXR1cm4gSU5UX01JTjsKICBpZihpPT1uKSByZXR1cm4gMDsKICBpbnQgbW4gPSAwOwogIGlmKGFbaV0+PTApIG1uID0gYVtpXSArIHNvbHZlKGkrMSxrLGRwLGEsdHJlZSk7CiAgZWxzZSBtbiA9IG1heChhW2ldICsgc29sdmUoaSsxLGssZHAsYSx0cmVlKSxzb2x2ZShpKzEsayAtIHF1ZXJ5KDAsbi0xLGksaSwwLHRyZWUpLGRwLGEsdHJlZSkpOwogIGRwW2ldW2tdID0gbW47CiAgcmV0dXJuIG1uOwp9CgoKaW50IG1haW4oKXsKCiAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgY2luLnRpZSgwKTsgY291dC50aWUoMCk7CgogIGludCB0OyBjaW4+PnQ7CiAgd2hpbGUodC0tPjApCiAgewogICAgY2luPj5uPj5rPj5tOwogICAgdmVjdG9yPGludD4gdHJlZSg1Km4sSU5UX01BWCksYShuKTsKCiAgICB2ZWN0b3I8dmVjdG9yPGludD4gPiBkcChuLHZlY3RvcjxpbnQ+KGssLTEpKTsKICAgIGZvcihpbnQgaT0wO2k8bjtpKyspIGNpbj4+YVtpXTsKCiAgICBmb3IoaW50IGk9MTtpPD1tO2krKyl7CiAgICAgIGludCBsLHIsYzsKICAgICAgY2luPj5sPj5yPj5jOwogICAgICB1cGRhdGUobCxyLDAsbi0xLDAsYyx0cmVlKTsKICAgIH0KCiAgICBjb3V0PDxzb2x2ZShrLDAsZHAsYSx0cmVlKTw8J1xuJzsKfQoKICByZXR1cm4gMDsKfQo=

MQo1IDEwIDUKMTAgLTIgLTUgNyAtMTAKMSAxIDUKMiA0IDEwCjQgNCAxMgozIDQgMTAKMSA1IDE1

1
5 10 5
10 -2 -5 7 -10
1 1 5
2 4 10
4 4 12
3 4 10
1 5 15