MasterChef

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef loves to prepare delicious dishes. He has prepared N dishes numbered from 1 to N for this year's MasterChef contest. He has presented all the N dishes to a panel of judges. Judging panel consists of M judges numbered from 1 to M. Rating for each dish was decided by voting from all the judges. Rating for the dishes has been given by a 1indexed array A where A_{i} denotes rating of the i^{th} dish.
Some dishes prepared by chef are extraordinary delicious, but unfortunately, some are not. Chef has been given a chance to improve the total rating of his dishes. By total rating of dishes, we mean the sum of the ratings of his dishes. Each of the M judges has administrative power to remove some (zero or more) dishes from a specified range. The i^{th} judge takes C_{i} rupees for removing each dish of Chef's choice from the dishes numbered from L_{i} to R_{i} (both inclusive). Once a dish is removed by any of the M judges it will not be considered for calculating total rating of the dishes. Chef has spent a large portion of his money preparing mouth watering dishes and has only K rupees left for now. Now chef is worried about maximizing total rating of his dishes by dropping some of the N dishes.
Please Help chef by finding the maximum total rating he can achieve such that the total expenditure does not exceed his budget of K rupees.
Input
 First line of input contains a single integer T denoting the number of test cases.
 First line of each test case contains three space separated integers N, K and M denoting the number of dishes prepared by chef, chef's budget, and number of judges in judging panel respectively.
 Next line of each test case contains N space separated integers where i^{th} integer denotes the rating received by the i^{th} dish.
 Next M lines of each test case contain three space separated integers each: L, R and C, where the integers in the i^{th} line denotes the value of L_{i}, R_{i} and C_{i} respectively.
Output
For each test case, print a single integer in a line corresponding to the answer.
Constraints
 1 ≤ T ≤ 10^{5}
 1 ≤ N,M ≤ 10^{5}
 1 ≤ K ≤ 500
 1 ≤ L_{i} ≤ R_{i} ≤ N
 1 ≤ C_{i} ≤ 200
 10^{9} ≤ A_{i} ≤ 10^{9}
 Sum of N and M over all test cases does not exceed 5*10^{5}
Subtasks :
 Subtask 1 : Sum of all N's across the test cases in a file does not exceed 5000. Sum of all M's is also at most 5000. (33 points).
 Subtask 2 : Sum of all N's across the test cases in a file does not exceed 5*10^{5}. Sum of all M's is also at most 5*10^{5}. ( 67 points ).
Example
input
1 5 10 5 10 2 5 7 10 1 1 5 2 4 10 4 4 12 3 4 10 1 5 15 output 5
Explanation
 Chef can drop dish numbered 3^{rd} with rating 5 by paying 10 rupees to the 4^{th} judge, and get the maximum possible total rating of 5.
Author:  ma5termind 
Tester:  mugurelionut 
Editorial  http://discuss.codechef.com/problems/MCHEF 
Tags  datastructure, dynamicprogramming, easymedium, july15, ma5termind 
Date Added:  2042015 
Time Limit:  1.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 