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 A_i is his rating in i^th 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 i^th judge demanded C_i amount of money for removing each match of swagger's choice in the range L_i to R_i (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 i^th integer denotes rating of i^th match

-Next M lines of each test case contains three integers: L,R and C where the integers in the i^th line denotes value L_i,R_i,C_i 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