# Parcels

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-office

_{i}and post-office

_{i-1}is (i-1)

^{th}element of array D.

There are P postmen. Each postman starts from post-office

_{1}and moves sequentially through all offices at a speed of 1 m/s (that is from post-office

_{1}to post-office

_{2}...to post-office

_{N}).When the postman is at post-office

_{i}(1<=i<=N), he collects all parcels that are presently in the post-office

_{i}. 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-office

_{1}and goes through all post offices till the Nth. Your task is to schedule the time leaving from post-office

_{1}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 j

_{i}and t

_{i}for the parcel

_{i}(1<=i<=M).

j

_{i}specifies the post office in which the parcel

_{i}is deposited.

t

_{i}specifies the time at which the parcel

_{i}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<= D

_{i}<=10

^{4}

1<= j

_{i}<=N

1<= t

_{i}<=10

^{4}

**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:**

Postman

_{1}leaves at 0 seconds from post-office

_{1}. Before leaving he collects the parcel

_{1}. At 1 second, he reaches post-office

_{2}and collects parcel

_{2}. At 9 seconds, he reaches post-office

_{4}and collects parcel

_{3}.

Postman

_{2}leaves post-office

_{1}at 10 seconds. He collects parcel

_{4}from post-office

_{1}. Now he reaches post-office

_{2}at 11 seconds and collects parcel

_{5}. Since the parcel

_{5}reached at 10 seconds, it waited for 1 second. Postman

_{2}reaches post-office

_{3}at 14 seconds collecting parcel

_{6}. Similarly, parcel

_{6}waits for 2 seconds.

Thus total waiting time :1+2=3.

*Problem Setter: Shradha Chhaparia*

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