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 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 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 genious . Help him maximize his rating within the budget constraint.
Thats a simple task of you. Isn't it ?
-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.
For each test case , print a single integer which is maximum possible sum in a new line
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
0 < T < 11
0 < N,M < 104
0 < K < 501
0 < Ci < 201
|Ai| <= 109
0 < Li <= Ri <= 10^4 but it is not in the range 0 < Li <= Ri <= N
TLE with top - down , AC with bottom-up...wasted a lot of time due to this ...
for 2nd test case he can bribe all the judges and not get any rating / rating of 0 rather than a negative rating..??
Were the test cases weak or the problem was supposed to be done in ******** (removed)