Zxr960115 是一个大农场的所有者。他喂养 m 只可爱的猫并使用 p 个喂食器。有一条笔直的路穿过农场,路边有n座小山,从左到右编号为1到n。山 i 和 (i - 1) 之间的距离为 di 米。喂食者住在 1 号山。
有一天,猫们出去玩。猫i去hill hi旅行,在时间ti完成旅行,然后在hill hi等待喂食器。喂食者必须带走所有的猫。每个喂食器都从 1 号山直接到达 n 号山,无需在山上等待,并将每座山上所有等待的猫带走。喂食者的行走速度为单位时间 1 米,并且足够强壮,可以带任意数量的猫。
例如,假设我们有两座山 (d2 = 1) 和一只猫,它于时间 3 在山 2 (h1 = 2) 完成了行程。然后,如果喂食者在时间 2 或时间 3 离开山 1,他可以带走这只猫,但如果他在时间 1 离开山 1,他就不能带走这只猫。如果喂食者在时间 2 离开山 1,猫等待他 0 时间单位,如果喂食者在时间 3 离开山 1,猫等待他 1 时间单位。
您的任务是安排每个喂食器从 1 号山出发的时间,以使所有猫的等待时间总和最小化。
输入
输入的第一行包含三个整数 n、m、p (2 ≤ n ≤ 105, 1 ≤ m ≤ 105, 1 ≤ p ≤ 100)。
第二行包含 n - 1 个正整数 d2, d3, ..., dn (1 ≤ di < 104)。
接下来的 m 行每行包含两个整数 hi 和 ti (1 ≤ hi ≤ n, 0 ≤ ti ≤ 109)。
输出
输出一个整数,所有猫等待时间的最小总和。
请不要编写 %lld 说明符来读取或写入 С++ 中的 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
4 6 2 1 3 5 1 0 2 1 4 9 1 10 2 10 3 12
输出 #1
3