Description

Original problem from: Codeforces Round #185 (Div. 1) B.

Little S is a farmer who owns $M$ cats and employs $P$ caretakers. There is a straight road on the farm with $N$ mountains numbered from $1$ to $N$. The distance between the $i$-th mountain and the $(i-1)$-th mountain is $D_i$. All caretakers live on mountain $1$.

One day, the cats went out to play. The $i$-th cat went to mountain $H_i$ and played until time $T_i$, then waited in place for a caretaker to pick it up. The caretakers must retrieve all the cats. Each caretaker walks along the road from mountain $1$ to mountain $N$, picking up all cats that are already waiting on each mountain. The caretakers take time to walk, moving at a speed of $1$ unit distance per unit time. The time taken to pick up cats on each mountain is negligible, and each caretaker can carry an infinite number of cats.

For example, suppose there are two mountains $1$ unit apart, and a cat plays on mountain $2$ until time $3$ before waiting. If a caretaker departs from mountain $1$ at time $2$ or $3$, they can pick up the cat, with the cat's waiting time being $0$ or $1$, respectively. However, if the caretaker departs at time $1$, they will pass mountain $2$ at time $2$ and cannot pick up the cat that is still playing at that time.

Your task is to plan the departure time for each caretaker from mountain $1$ such that the total waiting time of all cats is minimized. The departure time of a caretaker can be negative.

Input Format

The first line contains three integers $N$, $M$, $P$;
The second line contains $N-1$ positive integers $D_i$, representing the distance between the $i$-th mountain and the $(i-1)$-th mountain;
The next $M$ lines each contain two integers $H_i$ and $T_i$.

Output Format

Output an integer representing the answer.

Sample 1

4 6 2
1 3 5
1 0
2 1
4 9
1 10
2 10
3 12

3

Data Range and Hints

For all data, $2\le N\le 10^5$, $1\le M\le 10^5$, $1\le p\le 100$, $1\le D_i\lt 10^4$, $1\le H_i\le N$, and $0\le T_i\le 10^9$.