Description

Zxr960115 是一个大农场主。

他养了 m 只可爱的猫子,雇佣了 p 个铲屎官。这里有一条又直又长的道路穿过了农场，有 n 个山丘坐落在道路周围，编号自左往右从 1 到 n。山丘 i 与山丘 i-1的距离是 Di米。铲屎官们住在 1 号山丘。

一天，猫子们外出玩耍。猫子 i 去山丘Hi 游玩，在Ti时间结束他的游玩，然后在山丘Hi傻等铲屎官。铲屎官们必须把所有的猫子带上。每个铲屎官直接从H1走到Hn，中间不停下，可以认为不花费时间的把游玩结束的猫子带上。每个铲屎官的速度为一米每单位时间，并且足够强壮来带上任意数量的猫子。

举个栗子，假装我们有两个山丘( D2 =1 )，有一只猫子，他想去山丘 2 玩到时间 3。然后铲屎官如果在时间 2 或者时间 3 从 1 号山丘出发，他就能抱走猫子。如果他在时间 1 出发那么就不行(猫子还在玩耍)。如果铲屎官在时间 2 出发，猫子就不用等他（ΔT=0）。如果他在时间 3 出发，猫子就要等他 1 个单位时间。

你的任务是安排每个铲屎官出发的时间，最小化猫子们等待的时间之和。

Input Format

第一行输入三个整数n,m,p; 第二行输入n-1个整数d2,d3,....,dn； 接下m行输入两个数hi和ti;

Output Format

输出一个整数，表示最小化猫子们等待的时间之和。

Sample

样例输入：

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

样例输出：

3

Hint

对于全部数据满足： 2 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5, 1 ≤ p ≤ 100，1 ≤ di < 10^4,1 ≤ hi ≤ n, 0 ≤ ti ≤ 10^9