// Mugurel Ionut Andreica

#include <stdio.h>
#include <string.h>
#include <vector>
#include <set>

using namespace std;

#define NMAX 111111
#define KMAX 501

set<pair<int, int> > iset;
vector<int> add[NMAX], rem[NMAX];
int A[NMAX], C[NMAX];
long long ans, smin[KMAX];

int main() {
	int T, i, j, L, R, N, K, M, cost;
	scanf("%d", &T);
	while (T--) {
		scanf("%d %d %d", &N, &K, &M);
		for (ans = 0, i = 1; i <= N; i++) {
			scanf("%d", &A[i]);
			ans += A[i];
			add[i].clear();
			rem[i].clear();
		}
		for (i = 1; i <= M; i++) {
			scanf("%d %d %d", &L, &R, &C[i]);
			add[L].push_back(i);
			rem[R].push_back(i);
		}
		memset(smin, 0, sizeof(smin));
		iset.clear();
		for (i = 1; i <= N; i++) {
			for (j = 0; j < add[i].size(); j++)
				iset.insert(make_pair(C[add[i][j]], add[i][j]));
			if (A[i] < 0 && iset.size() > 0) {
				// cost is the minimum cost for removing the dish i. It is the minimum cost of an interval which includes the dish i.
				cost = iset.begin()->first;
				for (j = K - cost; j >= 0; j--)
					if (smin[j] + A[i] < smin[j + cost])
						smin[j + cost] = smin[j] + A[i];
			}
			for (j = 0; j < rem[i].size(); j++)
				iset.erase(make_pair(C[rem[i][j]], rem[i][j]));
		}
		printf("%lld\n", ans - smin[K]);
	}
	return 0;
}