CRICKDP - Cricket Selection

no tags

Swagger loves playing cricket and his its his dream to represent his
country at internatinal level . A cricket contest is being organised by
BCCI to select few top growing talents in country . He played "N" matches
and he was rated by selectors and also rating were given on basis of
voting through rabbler.Rating for his perormances is given below in 1
indexed array "A".
His performance in some of the matches were extraordinary but unfortunately
, some were total failure. Now he knows few "M" judges and 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 "Ci" amount of money for a
match each in the range "Li" to "Ri"(both inclusive). Ratings of removed match
will not be used in calculating ratings.
Now the real problem begins ,  he only has "K" amount of money. Now he wants to
increase his rating as high as possible . He is your friend and he also
knows that you are a genious .You are his only frined whom he can trust
and you are poor :P. Help him maximize his rating  within the  budget
constraint.
Thats a simple task of you . Isn't it ?

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 perormances are given below in 1 indexed array A where Ai is his rating in ith 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 incharge . The ith judge demanded Ci amount of money for removing each match of swagger's choice in the range Li to R(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 genious . Help him maximize his rating within the  budget constraint.

Thats a simple task of 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 ith integer denotes rating of ith match

-Next M lines of each test case contains three integers: L,R and C where the integers in the ith line denotes value Li,Ri,Ci 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 < 104`
`  0 < K < 501`
`  0 < Ci < 201`
`  |Ai| <= 109`