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.
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.
Print the minimum sum of waiting time of parcels.
No of test cases <=10
2<= N <=100
2<= M <=100
1<= P <=100
1<= Di <=104
1<= ji <=N
1<= ti <=104
4 6 2
1 3 5
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.
Problem Setter: Shradha Chhaparia