#include <bits/stdc++.h>
#include <fstream>
#define INF 800000000000
#define MOD 100000007
#define MAXN 100005
#define ins insert
#define pb push_back
#define mp make_pair
#define sz size
#define all(a) a.begin(), a.end()
#define rep(i, a, b) for(int i = a; i < b; ++i)
#define sd(n) scanf("%d",&n)
#define sll(n) scanf("%I64d",&n)
#define pdn(n) printf("%d\n",n)
#define plln(n) printf("%I64d\n",n)
#define pd(n) printf("%d ",n)
#define nl() printf("\n")
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;

namespace patch
{
    template < typename T > std::string to_string( const T& n )
    { 
        std::ostringstream stm ;
        stm << n ;
        stm.str() ;
    }
}

ll modpow(ll base, ll exponent, int modulus)
{
    ll result = 1;
    while (exponent > 0)
    {
        if (exponent % 2 == 1)
            result = (result * base) % modulus;
        exponent = exponent >> 1;
        base = (base * base) % modulus;
    }
    return result;
}

ll gcd(ll u, ll v)
{
    return (v != 0) ? gcd(v, u % v) : u;
}

int t, n, k, m, score[10001];
vvi ad(10001), del(10001);
multiset<int> mm;
ll mincost[10001], dp[10001][501];

/*ll solve(int idx, int rem) {
    if(rem < 0)
        return -50000000LL;
    if(idx == 0)
        return 0;
    if(dp[idx][rem] != 800000000LL)
        return dp[idx][rem];
    return dp[idx][rem] = max(solve(idx-1, rem-mincost[idx]), solve(idx-1, rem)+(ll)score[idx]);
}*/

int main() {
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);
    //cout.tie(0);
    sd(t);
    while(t--) {
        mm.clear();
        rep(i, 0, 10001) {
            rep(j, 0, 501)
                dp[i][j] = 0;
            ad[i].clear();
            del[i].clear();    
        }
        sd(n); sd(k); sd(m);
        rep(i, 1, n+1)
            scanf("%d", &score[i]);
        rep(i, 0, m) {
            int l, r, c;
            sd(l); sd(r); sd(c);
            ad[l].pb(c);
            del[r].pb(c);
        }
        mm.ins(k+5);
        rep(i, 1, n+1) {
            rep(j, 0, ad[i].sz()) {
                mm.ins(ad[i][j]);
            }
            mincost[i] = *mm.begin();
            rep(j, 0, del[i].sz()) {
                mm.erase(mm.find(del[i][j]));
            }
        }
        //rep(i, 1, n+1)
        //    cout << mincost[i] << endl;
        dp[0][0] = 0LL;
        rep(i, 1, n+1)
            dp[i][0] = dp[i-1][0] + (ll)score[i];
        rep(i, 1, n+1) {
            rep(j, 1, k+1) {
                if(j >= mincost[i])
                    dp[i][j] = max(dp[i-1][j]+(ll)score[i], dp[i-1][j-mincost[i]]);
                else
                    dp[i][j] = dp[i-1][j]+(ll)score[i];
            }
        }      
        printf("%lld\n", dp[n][k]);  
    }
    return 0;
}