Swagger loves playing cricket and its his childhood dream to represent his country at international level. A cricket tournament is being organised by BCCI to select few young talents in country. He played N matches and he was rated by selectors and public on basis of his performance in each match. Rating for his performances are given below in 1 indexed array A where A_i is his rating in i^th match.

His performance in some of the matches were extraordinary but unfortunately, some were total failure. Now swagger has a chance to improve his total rating which is sum of ratings in each of the matches. As he knows some of M judges, he tried to bribe them and finally they agreed to remove the rating of few matches where they were in charge. The i^th judge demanded C_i amount of money for removing each match of swagger's choice in the range L_i to R_i (both inclusive). Ratings of removed match will not be used in calculating total rating.

Now the real problem begins, he only has K amount of money and he wants to increase his total rating as high as possible. He is your friend and he also knows that you are a genius. Help him maximise his rating within the budget constraint.

That's a simple task for you, isn't it?

Input

First line contains number of test cases T.

First line of each test case contains 3 space separated integer N, K, M denoting Number of matches he played, amount of money he has and number of judges he can bribe.

Next line contains N space separated integers where i^th integer denotes rating of i^th match.

Next M lines of each test case contains three integers: L, R and C where the integers in the i^th line denotes value L_i, R_i, C_i respectively.

Output

For each test case, print a single integer which is maximum possible sum in a new line.

Example

Input:
2
5 7 5
5 -4 3 -3 3
1 1 5
1 3 2
2 4 5
1 5 7
3 3 2
5 10 2
-1 -2 -3 -4 -5
1 3 3
3 4 4

Output:
11
-6

Constraints

0 < T < 11

0 < N, M < 10⁴

0 < K < 501

0 < C_i < 201

|A_i| <= 10⁹