题目描述

原题来自：Codeforces Round #185 (Div. 1) B.

小 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\)。

输出格式

输出一个整数表示答案。

样例数据

样例输入

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

样例输出

3

限制与提示

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