#10187. 「一本通 5.6 例 4」Cats Transport

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 1bentong

题目描述

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

小 S 是农场主,他养了 MM 只猫,雇了 PP 位饲养员。农场中有一条笔直的路,路边有 NN 座山,从 11NN 编号。第 ii 座山与第 i1i-1 座山之间的距离是 DiD_i。饲养员都住在 11 号山上。

有一天,猫出去玩。第 ii 只猫去 HiH_i 号山玩,玩到时刻 TiT_i 停止,然后在原地等饲养员来接。饲养员们必须回收所有的猫。每个饲养员沿着路从 11 号山走到 NN 号山,把各座山上已经在等待的猫全部接走。饲养员在路上行走需要时间,速度为 11 米每单位时间。饲养员在每座山上接猫的时间可以忽略,可以携带的猫的数量为无穷大。

例如有两座相距为 11 的山,一只猫在 22 号山玩,玩到时刻 33 开始等待。如果饲养员从 11 号山在时刻 2233 出发,那么他可以接到猫,猫的等待时间为 0011。而如果他于时刻 11 出发,那么他将于时刻 22 经过 22 号山,不能接到当时仍在玩的猫。

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

输入格式

第一行三个整数 N,M,PN,M,P
第二行 N1N-1 个正整数 DiD_i,表示第 ii 座山与第 i1i-1 座山之间的距离是 DiD_i
接下去 MM 行每行两个整数 Hi,TiH_i,T_i

输出格式

输出一个整数表示答案。

样例

样例输入

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

样例输出

3

数据范围与提示

对于全部数据,2N105,1M105,1p100,1Di<104,1HiN,0Ti1092\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