题目描述

小$S$是农场主，他养了$M$只猫，雇了$P$位饲养员。

农场中有一条笔直的路，路边有 $N$ 座山，从 1 到 $N$ 编号。

第$i$ 座山与第$i$−1 座山之间的距离为$D_i$。

饲养员都住在 1 号山。

有一天，猫出去玩。

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

饲养员们必须回收所有的猫。

每个饲养员沿着路从 1 号山走到 $N$号山，把各座山上已经在等待的猫全部接走。

饲养员在路上行走需要时间，速度为 1 米/单位时间。

饲养员在每座山上接猫的时间可以忽略，可以携带的猫的数量为无穷大。

例如有两座相距为 1 的山，一只猫在 2 号山玩，玩到时刻 3 开始等待。

如果饲养员从 1 号山在时刻 2 或 3 出发，那么他可以接到猫，猫的等待时间为 0 或 1。

而如果他于时刻 1 出发，那么他将于时刻 2 经过 2 号山，不能接到当时仍在玩的猫。

你的任务是规划每个饲养员从 1 号山出发的时间，使得所有猫等待时间的总和尽量小。

饲养员出发的时间可以为负。

输入格式

第一行包含三个整数 $N，M，P$。

第二行包含$n$−1 个整数，$D_2,D_3,…,D_N$。

接下来 $M$ 行，每行包含两个整数 $H_i$ 和 $T_i$。

输出格式

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

样例

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

3

数据范围

$2≤N≤10^5, 1≤M≤10^5, 1≤P≤100, 1≤D_i<10000, 1≤H_i≤N, 0≤T_i≤10^9$

来源

• 算法竞赛进阶指南