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

hide comments
Thotsaphon Thanatipanonda: 2016-01-07 16:35:03

0 < Li <= Ri <= 10^4 but it is not in the range 0 < Li <= Ri <= N
This made me waste a lot of time.

SUBHAJIT GORAI: 2016-01-04 17:53:22

TLE with top - down , AC with bottom-up...wasted a lot of time due to this ...

naruto09: 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
maverick_10: 2015-12-22 23:17:34

my 100th
score = 10.1
****** + ******* (no spoilers allowed)

Last edit: 2015-12-23 12:53:12
Prateek Agarwal: 2015-12-17 12:49:12

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

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