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 performances 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 in charge. The ith judge demanded Ci amount of money for removing each match of swagger's choice in the range Li to Ri (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 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


Added by:Adarsh kumar
Date:2015-12-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Added by saurabh_29

hide comments
2016-01-07 16:35:03 Thotsaphon Thanatipanonda
0 < Li <= Ri <= 10^4 but it is not in the range 0 < Li <= Ri <= N
This made me waste a lot of time.
2016-01-04 17:53:22 SUBHAJIT GORAI
TLE with top - down , AC with bottom-up...wasted a lot of time due to this ...
2015-12-27 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..??

(reply)=> You dont have enough money to do that ! Read the problem statement carefully.

Last edit: 2015-12-27 15:00:47
2015-12-22 23:17:34
my 100th
score = 10.1
****** + ******* (no spoilers allowed)

Last edit: 2015-12-23 12:53:12
2015-12-17 12:49:12 Prateek Agarwal
Were the test cases weak or the problem was supposed to be done in ******** (removed)

(reply)=> some of the cases :p

Last edit: 2015-12-22 09:57:49
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.