CRICKDP  Cricket Selection
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 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 incharge . 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 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 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^{4}
0 < K < 501
0 < C_{i} < 201
A_{i} <= 10^{9}
hide comments
Thotsaphon Thanatipanonda:
20160107 16:35:03
0 < Li <= Ri <= 10^4 but it is not in the range 0 < Li <= Ri <= N


SUBHAJIT GORAI:
20160104 17:53:22
TLE with top  down , AC with bottomup...wasted a lot of time due to this ... 

naruto09:
20151227 07:01:57
for 2nd test case he can bribe all the judges and not get any rating / rating of 0 rather than a negative rating..??


maverick_10:
20151222 23:17:34
my 100th


Prateek Agarwal:
20151217 12:49:12
Were the test cases weak or the problem was supposed to be done in ******** (removed)

Added by:  Adarsh kumar 
Date:  20151214 
Time limit:  0.25s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  Added by saurabh_29 