题目描述

小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_i$，表示第i座山与第i-1座山之间的距离是$D_i$； 接下去M行每行两个整数$H_i,T_i$。

输出描述

输出一个整数表示答案。

示例1

输入

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

输出

3

备注

对于全部数据，$2 \leq N \leq 10^5,1 \leq M \leq 10^5,1 \leq p \leq 100,1 \leq D_i \lt 10^4,1 \leq H_i \leq N,0 \leq T_i \leq 10^9$。