题目描述

Zxr960115 是一个大农场主。

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

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

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

你的任务是安排每个铲屎官出发的时间(可以从 0 时刻之前出发），最小化猫子们等待的时间之和。

对于全部的数据，满足 $2\le n\le10^5$，$1\le m\le10^5$，$1\le p\le100$，$1\le d_i<10^4$，$1\le h_i\le n$，$0\le t_i \le10^9$

输入格式

第一行三个整数 $n,m,p$ ，$(2 \le n\le 10^5,1 \le m \le 10^5, 1\le p \le 100)$.

第二行 $n-1$ 个正整数 $d_{2},d_{3},...,d_{n}$ $(1 \le d_{i} < 10^{4}) .$

接下去 $m$ 行每行两个整数$h_i$ 和$t_i$ $(1 \le h_i \le n,0 \le t_i \le 10^9)$.

输出格式

输出一个整数表示答案。

样例 #1

样例输入 #1

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

样例输出 #1

3