#214. 运输小猫

运输小猫

题目描述

小S是农场主,他养了 M\red {M} 只猫,雇了 P\red {P} 位饲养员。

农场中有一条笔直的路,路边有 N\red {N} 座山,从 1\red {1}N\red {N} 编号。

i\red {i} 座山与第 i1\red {i-1} 座山之间的距离为 Di\red {D_i}

饲养员都住在 1\red {1} 号山。

有一天,猫出去玩。

i\red {i} 只猫去 Hi\red {H_i} 号山玩,玩到时刻 Ti\red {T_i} 停止,然后在原地等饲养员来接。

饲养员们必须回收所有的猫。

每个饲养员沿着路从 1\red {1 }号山走到 N\red {N }号山,把各座山上已经在等待的猫全部接走。

饲养员在路上行走需要时间,速度为1\red {1} 米/单位时间。

饲养员在每座山上接猫的时间可以忽略,可以携带的猫的数量为无穷大。

例如有两座相距为 1\red {1 }的山,一只猫在 2\red {2 }号山玩,玩到时刻 3\red {3 }开始等待。

如果饲养员从 1\red {1 }号山在时刻 2\red {2 }3\red {3 }出发,那么他可以接到猫,猫的等待时间为 0\red {0 }1\red {1}

而如果他于时刻 1\red {1} 出发,那么他将于时刻 2\red {2 }经过 2\red {2 }号山,不能接到当时仍在玩的猫。

你的任务是规划每个饲养员从 1\red {1 }号山出发的时间,使得所有猫等待时间的总和尽量小。

饲养员出发的时间可以为负。

输入格式

第一行包含三个整数N\red {N}M\red {M}P\red {P}

第二行包含n1\red {n-1}个整数,D2,D3,,DN\red {D_2 ,D_3 ,…,D_N}

接下来M\red {M}行,每行包含两个整数Hi\red {H_i}Ti\red {T_i}

输出格式

输出一个整数,表示所有猫等待时间的总和的最小值。

样例

输入样例

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

输出样例

3

提示

2N105\red {2≤N≤10^5},

1M105\red {1≤M≤10^5},

1P100\red {1≤P≤100},

1Di<1000\red {1≤D_i <1000},

1HiN\red {1≤H_i ≤N},

0Ti109\red {0≤T_i ≤10^9}