好的，我们整理成一道清晰的题目。

---

题目描述

小 S 有一个农场，养了 $M$ 只猫，雇了 $P$ 位饲养员。

农场中有一条笔直的路，路边有 $N$ 座山，从 $1$ 到 $N$ 编号。
第 $i$ 座山与第 $i-1$ 座山之间的距离为 $D_i$（$i \ge 2$），已知 $D_2, D_3, \dots, D_N$。

饲养员们都住在 $1$ 号山。

猫会出去玩：第 $i$ 只猫去 $H_i$ 号山玩，玩到时刻 $T_i$ 停止，然后就在原地等待饲养员来接。

饲养员必须把所有猫都接回来。
每个饲养员从 $1$ 号山出发，以速度 $1$ 单位距离/单位时间，沿着路走到 $N$ 号山。
饲养员在每座山可以立刻接走该山上已经在等待的猫，且携带猫的数量不限。

如果一只猫在 $H_i$ 号山，玩到时刻 $T_i$，而饲养员在时刻 $S$ 从 $1$ 号山出发，那么：

• 饲养员到达 $H_i$ 号山的时刻为 $S + \text{dist}(1, H_i)$，其中 $\text{dist}(1, H_i)$ 表示从 $1$ 号山到 $H_i$ 号山的距离。
• 猫的等待时间为 $S + \text{dist}(1, H_i) - T_i$（如果这个值 $\ge 0$），否则不能接上（必须保证到达时间 $\ge T_i$）。

注意：

• 饲养员的出发时间可以是负数（例如提前出发）。
• 每个饲养员可以接走沿途所有已经在等待的猫。
• 目标是规划 $P$ 位饲养员的出发时间（饲养员之间出发时间可以不同），使得所有猫的等待时间总和最小。
• 数据保证有解（$P \ge 1$，且饲养员数量足够接完所有猫）。

---

输入格式

第一行三个整数 $N, M, P$。
第二行包含 $N-1$ 个整数 $D_2, D_3, \dots, D_N$（表示第 $i-1$ 到 $i$ 的距离）。
接下来 $M$ 行，每行两个整数 $H_i, T_i$。

输出格式

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

数据范围

• $2 \le N \le 10^5$
• $1 \le M \le 10^5$
• $1 \le P \le 100$
• $1 \le D_i < 10000$
• $1 \le H_i \le N$
• $0 \le T_i \le 10^9$

---

输入样例

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

输出样例

3

---

样例解释

$N=4$ 座山，$M=6$ 只猫，$P=2$ 个饲养员。

距离（从 $1$ 号山算起的累积距离）：

• $D_2 = 1$ → 山 $1$ 到山 $2$ 距离 = $1$
• $D_3 = 3$ → 山 $2$ 到山 $3$ 距离 = $3$，山 $1$ 到山 $3$ 距离 = $1+3=4$
• $D_4 = 5$ → 山 $3$ 到山 $4$ 距离 = $5$，山 $1$ 到山 $4$ 距离 = $1+3+5=9$

所以 $\text{dist}(1, H)$：

• $H=1$ → 0
• $H=2$ → 1
• $H=3$ → 4
• $H=4$ → 9

猫的信息（$H_i, T_i$）：

1. $(1, 0)$ — 到达时间必须 $\ge 0$，实际出发时间 $S \ge 0$
2. $(2, 1)$ — 到达时间 $\ge 1$ → $S+1 \ge 1$ → $S \ge 0$
3. $(4, 9)$ — 到达时间 $\ge 9$ → $S+9 \ge 9$ → $S \ge 0$
4. $(1, 10)$ — $S+0 \ge 10$ → $S \ge 10$
5. $(2, 10)$ — $S+1 \ge 10$ → $S \ge 9$
6. $(3, 12)$ — $S+4 \ge 12$ → $S \ge 8$

为了简化：
定义猫的“实际必须接的时刻”为 $a_i = T_i - \text{dist}(1, H_i)$，即饲养员的出发时间 $S \ge a_i$ 才能接到猫，猫等待时间 = $S - a_i$。

计算 $a_i$：

1. $0 - 0 = 0$
2. $1 - 1 = 0$
3. $9 - 9 = 0$
4. $10 - 0 = 10$
5. $10 - 1 = 9$
6. $12 - 4 = 8$

所以 $a = [0, 0, 0, 10, 9, 8]$，按从小到大排序（题意其实应该先按 $a_i$ 排序）： 排序后 $a = [0, 0, 0, 8, 9, 10]$。

现在问题变为：有 $M$ 个“任务” $a_i$（单调不减），要分成 $P$ 组，每组由一个饲养员在时刻 $S_j$ 出发，该组的猫等待时间之和 = $\sum_{i \in \text{group}_j} (S_j - a_i)$，要求 $S_j \ge a_i$，目标是总等待时间最小。

最优时 $S_j$ 取为该组中最大的 $a_i$，这样等待时间最少。

于是问题变成：将 $a$ 序列分成 $P$ 段，每段代价 = 该段最大值 × 长度 - 该段 $a_i$ 之和。

对于排序后的 $a$：$[0, 0, 0, 8, 9, 10]$，前缀和 $sum = [0, 0, 0, 8, 17, 27]$（累加）。

---

用 $P=2$ 分：

分法1：

• 第一段 $[0,0,0]$：最大值 0，长度 3，和 0，代价 = $0\times 3 - 0 = 0$
• 第二段 $[8,9,10]$：最大值 10，长度 3，和 27，代价 = $10\times 3 - 27 = 30 - 27 = 3$ 总代价 = $0 + 3 = 3$

分法2：

• 第一段 $[0,0,0,8]$：最大值 8，长度 4，和 8，代价 = $8\times 4 - 8 = 32 - 8 = 24$
• 第二段 $[9,10]$：最大值 10，长度 2，和 19，代价 = $10\times 2 - 19 = 20 - 19 = 1$ 总代价 = $25$，更大。

显然最小是 $3$。

所以样例输出为 $3$。