2889: 「一本通 5.6 例 4」Cats Transport

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:13 Solved:6

Description

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

小 S 是农场主,他养了 MMM 只猫,雇了 PPP 位饲养员。农场中有一条笔直的路,路边有 NNN 座山,从 111NNN 编号。第 iii 座山与第 i−1i-1i1 座山之间的距离是 DiD_iDi。饲养员都住在 111 号山上。

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

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

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

Input

第一行三个整数 N,M,PN,M,PN,M,P
第二行 N−1N-1N1 个正整数 DiD_iDi,表示第 iii 座山与第 i−1i-1i1 座山之间的距离是 DiD_iDi
接下去 MMM 行每行两个整数 Hi,TiH_i,T_iHi,Ti

Output

输出一个整数表示答案。

HINT

样例输入

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

样例输出

3

对于全部数据,2≤N≤105,1≤M≤105,1≤p≤100,1≤Di<104,1≤Hi≤N,0≤Ti≤1092le Nle 10^5,1le Mle 10^5,1le ple 100,1le D_ilt 10^4,1le H_ile N,0le T_ile 10^92N105,1M105,1p100,1Di<104,1HiN,0Ti109

加入题单

上一题 下一题 算法标签: