问题 22745 --观光公交

22745: 观光公交

时间限制: 1 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

某个公交车线路有 N 个站点(但只有1辆车),从第 i 个站点到第 i+1 个站点需要 D[i] 单位时间。现在有 M 名旅客需要搭乘公交车,每位旅客于 T[i] 时间到达 A[i] 车站,并搭乘公交车前往 B[i] 车站。 由于顾客是上帝,所以公交车会等待在该站点上车的所有旅客都上车,然后才继续出发。旅客们都抱怨等待时间(每位旅客到达车站的时间 T[i] 直到旅客到站下车的时间)太长。为了使等待时间缩短,公交车上配备了 K 颗加速器。每使用一个加速器,可以使 D[i] 缩短 1 个单位时间,但前提是D[i]>=0。求在合理使用加速器的情况下,所有旅客等待的总时间的最小值。

输入

输入第一行是三个整数 N,M,K 。

第二行含 N-1 个整数,每个整数表示 i 站到 i+1 站所需要的时间 D[i] 。

之后的 M 行每行是一个旅客的到达站点时间 T[i] ,出发站点 A[i] ,目标站点 B[i]。

输出

输出所有旅客等待的总时间的最小值。

样例输入

3 3 2
1 4
0 1 3
1 1 2
5 2 3

样例输出

10

提示

输入输出样例说明:


在第2站与第3站间使用加速器,使时间缩短为2。


巴士于t=1时从1出发,t=2时到达2;t=5时从2出发,t=7时到达3。


三名乘客的等待时间分别是7-0=7, 2-1=1, 7-5=2,总等待时间为10。


数据范围:


10% k=0


20% k=1 


40% 2<=n<=50, 1<=m<=1000, 0<=k<=20, 0<=Di<=10, 0<=Ti<=500


60% 1<=n<=100, 1<=m<=1000, 0<=k<=100, 0<=Di<=100, 0<=Ti<=10000


100% 1<=n<=1000, 1<=m<=10000, 0<=k<=100,000, 0<=Di<=100, 0<=Ti<=100,000


NOIP2011 DAY2 bus

来源

[提交][状态]