题目背景
感谢@Transhumanist 提供的一组Hack数据
题目描述
风景迷人的小城Y 市，拥有n 个美丽的景点。由于慕名而来的游客越来越多，Y $市特意安排了一辆观光公交车，为游客提供更便捷的交通服务。观光公交车在第 $0 $分钟出现在 $1号景点，随后依次前往$ 2,3 ,4 ,…,n$ 号景点。从第 i $号景点开到第 i+1$ 号景点需要$ D_i $分钟。任意时刻，公交车只能往前开，或在景点处等待。
设共有m 个游客，每位游客需要乘车1次从一个景点到达另一个景点，第i $位游客在T_i 分钟来到景点 $A_i $，希望乘车前往景点B_i (A_i
假设乘客上下车不需要时间。一个乘客的旅行时间，等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一辆观光车，有时候还要停下来等其他乘客，乘客们纷纷抱怨旅行时间太长了。于是聪明的司机ZZ给公交车安装了k个氮气加速器，每使用一个加速器，可以使其中一个$ D_i-1$ 。对于同一个Di 可以重复使用加速器，但是必须保证使用后Di≥0 。
那么ZZ该如何安排使用加速器，才能使所有乘客的旅行时间总和最小？
输入输出格式
输入格式：
第1行是3个整数n,m,k ，每两个整数之间用一个空格隔开。分别表示景点数、乘客数和氮气加速器个数。
第2行是n−1个整数，每两个整数之间用一个空格隔开，第i $个数表示从第i$ 个景点开往第i+1 个景点所需要的时间，即$ D_i $。
第3 $行至m+2$ 行每行3 $个整数 $T_i, A_i, B_i，每两个整数之间用一个空格隔开。第$ i+2$ 行表示第i 位乘客来到出发景点的时刻，出发的景点编号和到达的景点编号。
输出格式：
一个整数，表示最小的总旅行时间。
输入输出样例
输入样例#1：
3 3 2
1 4
0 1 3
1 1 2
5 2 3
输出样例#1：
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。
noip2011提高组day2第3题