题目描述

Zxr960115 是一个大农场主，他饲养了 $m$ 只可爱的猫咪，并雇用了 $p$ 名饲养员。农场中有一条笔直的道路，道路旁有 $n$ 座山丘，从左到右依次编号为 $1$ 到 $n$。第 $i$ 座山丘与第 $(i-1)$ 座山丘之间的距离为 $d_{i}$ 米。所有饲养员都居住在山丘 $1$。

某天，猫咪们外出玩耍。第 $i$ 只猫咪前往山丘 $h_{i}$，并在时间 $t_{i}$ 结束游玩，随后在山丘 $h_{i}$ 等待饲养员接它。饲养员必须接走所有猫咪。每位饲养员从山丘 $1$ 走向山丘 $n$，途中不在任何山丘停留，并带走途中每个山丘上所有等待的猫咪。饲养员的行走速度为 $1$ 米/单位时间，且他们的运输能力足够强，可以携带任意数量的猫咪。

例如，假设有两座山丘（$d_{2}=1$）和一只猫咪，该猫咪在时间 $3$ 结束游玩于山丘 $2$（$h_{1}=2$）。若饲养员在时间 $2$ 或时间 $3$ 离开山丘 $1$，则能接到这只猫咪；但若在时间 $1$ 离开则无法接到。若饲养员在时间 $2$ 出发，猫咪的等待时间为 $0$；若在时间 $3$ 出发，猫咪的等待时间为 $1$。

你的任务是规划每位饲养员从山丘 $1$ 出发的时间，使得所有猫咪的等待时间总和最小。

输入格式

第一行包含三个整数 $n,m,p$。

第二行包含 $n-1$ 个正整数 $d_{2},d_{3},...,d_{n}$。

接下来的 $m$ 行，每行包含两个整数 $h_i$ 和 $t_i$。

输出格式

输出一个整数，表示所有猫咪的最小等待时间总和。

请注意：在 C++ 中读写 64 位整数时，请勿使用 %lld 标识符。建议使用 cin/cout 流或 %I64d 标识符。

输入输出样例 #1

输入 #1

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

输出 #1

3

说明/提示

对于 $100\%$ 的数据，$2 \le n \le 10^5,\ 1 \le m \le 10^5,\ 1 \le p \le 100, 1 \le d_{i} < 10^4,1 \le h_i \le n,\ 0 \le t_i \le 10^9$。