ACM has decided to organize an event. For the same purpose, it awaits M urgent parcels from different companies. When a company couriers a parcel it deposits it in the closest post-office. There are N post offices in the city numbered from 1 to N. The distance between post-officei and post-officei-1 is (i-1)th element of array D.
There are P postmen. Each postman starts from post-office1 and moves sequentially through all offices at a speed of 1 m/s (that is from post-office1 to post-office2 ...to post-officeN).When the postman is at post-officei (1<=i<=N), he collects all parcels that are presently in the post-officei. He does not wait at the post-office for any parcel. Once a postman reaches a post office it takes 0 seconds for the postman to collect the parcels from the post office and then he moves to the next. The time span between the arrival of a parcel at a post-office and its collection by a postman is the waiting time of that parcel.
Each postman can start at a different time from post-office1 and goes through all post offices till the Nth. Your task is to schedule the time leaving from post-office1 for each postman so that the sum of the waiting time of all parcels is minimized.

Input:
The first line contains the number of test cases T.
For each test case, the first line contains three numbers N,M,P.
The next line contains N-1 integers representing array D, the inter-distance between post offices.
The next M line contains 2 integers ji and ti for the parceli(1<=i<=M).
ji specifies the post office in which the parceli is deposited.
ti specifies the time at which the parceli is deposited in the post office.

Output:
Print the minimum sum of waiting time of parcels.

Constraints:
No of test cases <=10
2<= N <=100
2<= M <=100
1<= P <=100
1<= Di <=104
1<= ji <=N
1<= ti <=104

Sample input:
1
4 6 2
1 3 5
1 0
2 1
4 9
1 10
2 10
3 12

Sample Output:
3

Explanation:
Postman1 leaves at 0 seconds from post-office1. Before leaving he collects the parcel1. At 1 second, he reaches post-office2 and collects parcel2. At 9 seconds, he reaches post-office4 and collects parcel3.
Postman2 leaves post-office1 at 10 seconds. He collects parcel4 from post-office1. Now he reaches post-office2 at 11 seconds and collects parcel5. Since the parcel5 reached at 10 seconds, it waited for 1 second. Postman2 reaches post-office3 at 14 seconds collecting parcel6. Similarly, parcel6 waits for 2 seconds.
Thus total waiting time :1+2=3.

Languages: AWK,Bash,Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Python3,Ruby,Text

Time Limit: 5 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0