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
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
|
|
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..??
|
|
maverick_10:
2015-12-22 23:17:34
my 100th
|
|
Prateek Agarwal:
2015-12-17 12:49:12
Were the test cases weak or the problem was supposed to be done in ******** (removed)
|
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 |