题目描述
风景迷人的小城Y市，拥有n 个美丽的景点。由于慕名而来的游客越来越多，Y市特意安排了一辆观光公交车，为游客提供更便捷的交通服务。观光公交车在第 0分钟出现在 1号景点，随后依次前往2,3 ,4 ,…,n 号景点。从第 i号景点开到第i+1号景点需要Di分钟。任意时刻，公交车只能往前开，或在景点处等待。
设共有m个游客，每位游客需要乘车1次从一个景点到达另一个景点，第i位游客在Ti分钟来到景点 Ai，希望乘车前往景点Bi(Ai假设乘客上下车不需要时间。一个乘客的旅行时间，等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一辆观光车，有时候还要停下来等其他乘客，乘客们纷纷抱怨旅行时间太长了。于是聪明的司机ZZ给公交车安装了k个氮气加速器，每使用一个加速器，可以使其中一个Di−1 。对于同一个Di 可以重复使用加速器，但是必须保证使用后Di≥0 。
那么ZZ该如何安排使用加速器，才能使所有乘客的旅行时间总和最小？
输入
第1行是3个整数n, m, k，每两个整数之间用一个空格隔开。分别表示景点数、乘客数和氮气加速器个数。
第2行是n-1个整数，每两个整数之间用一个空格隔开，第i个数表示从第i个景点开往第i+1 个景点所需要的时间，即Di。
第3行至m+2 行每行3个整数 Ti,Ai,Bi，每两个整数之间用一个空格隔开。第i+2 行表示第i位乘客来到出发景点的时刻，出发的景点编号和到达的景点编号。
输出
一个整数，表示最小的总旅行时间。
样例输入
3 3 2
1 4
0 1 3
1 1 2
5 2 3
样例输出
10
提示
【输入输出样例说明】
对D2 使用2 个加速器，从2号景点到 3 号景点时间变为 2 分钟。
公交车在第1 分钟从1 号景点出发，第2 分钟到达2 号景点，第5 分钟从2 号景点出发，第7 分钟到达 3 号景点。
第1个旅客旅行时间 7-0=7分钟。
第2个旅客旅行时间 2-1=1 分钟。
第3个旅客旅行时间 7-5 = 2分钟。
总时间7+1+2 = 10分钟。
【数据范围】
对于10% 的数据，k=0；
对于20%的数据，k=1 ；
对于40% 的数据，2≤n≤50,1≤m≤1,000,0≤k≤20,0≤Di≤10,0≤Ti≤500；
对于60%的数据，1≤n≤100,1≤m≤1,000,0≤k≤100,0≤Di≤100,0≤Ti≤10,000；
对于100%的数据，1≤n≤1,000,1≤m≤10,000,0≤k≤100,000,0≤Di≤1000≤Ti≤100,000。
来源/分类
NOIP提高组 NOIP2011