Shivam Sir is a lover of animals , and he bought a zoo to stay close to them . His zoo has multiple sections , and each section contains animals . Animals can be either normal or scary . A section can contain both normal and scary animals . The local kindergarden schools want to visit the zoo but because the children are very young , they dont want to show them the scary animals . Hence , the schools send their itinerary to Shivam Sir and request him to remove the scary animals from the sections they are to visit . Each school's itinerary consists of the sections they are to visit , and each school visits any number of contiguous sections only. Each school quotes its own price that it will pay for the visit and there is a fixed cost of removing the scary animals from each section . All the schools visit on the same day , so Shivam Sir needs to remove the scary animals from any section only once for any number of schools to visit it . Now Shivam Sir doesnt want to incur a loss , so he removes the scary animals only if he can gain an overall profit by the schools visiting . He can then tell any particular school not to visit if he is not recieving any profit by their visit . You have to tell the maximum profit he can make .
Note : You may decide not to move animals from any zoo and so there is no gain.
Input
The first line contains an integer T denoting the number of test cases. First line of test cases contains two integers N and M denoting the number of section and the number of schools respectively.
Next line contains N space separated integers where the ith integer denotes the money required to move scary animals from the ith section.
Then M lines follow. Each line contains three integers L , R , C where the jth line denotes that the jth school will visit all the section from L to R, inclusive, and will pay the owner C money for the visit .
Output
Print a single integer denoting the maximum profit the owner can make.
Constraints
1 <= T <= 100
1 <= N ,M <= 105
0 <= X <= 109
1 <= L <= R <= N
1 <= C <= 109
Explanation Case 1: Optimal solution would be to move dangerous animals from zoo numbered ( 1, 2, 3, 7). Three schools wil come to visit which gives profit of 15 and the moving of animals costs 11, hence the total profit is 4.
