[NOIP2011-提高] 观光公交

题目背景

感谢@Transhumanist 提供的一组Hack数据

题目描述

风景迷人的小城$Y$ 市，拥有$n$ 个美丽的景点。由于慕名而来的游客越来越多，Y $市特意安排了一辆观光公交车，为游客提供更便捷的交通服务。观光公交车在第 $0 $分钟出现在 $1号景点，随后依次前往$ 2,3 ,4 ,\dots,n$ 号景点。从第 i $号景点开到第 i+1$ 号景点需要$ D_i $分钟。任意时刻，公交车只能往前开，或在景点处等待。

设共有$m$ 个游客，每位游客需要乘车$1$次从一个景点到达另一个景点，第i $位游客在T_i 分钟来到景点 $A_i $，希望乘车前往景点B_i (A_i

假设乘客上下车不需要时间。一个乘客的旅行时间，等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一辆观光车，有时候还要停下来等其他乘客，乘客们纷纷抱怨旅行时间太长了。于是聪明的司机$ZZ$给公交车安装了$k$个氮气加速器，每使用一个加速器，可以使其中一个$ D_i-1$ 。对于同一个$D_i$ 可以重复使用加速器，但是必须保证使用后$D_i \ge 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

说明

【输入输出样例说明】

对$D_2$ 使用$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 \leq n \leq 50,1 \leq m \leq 1,000,0 \leq k \leq 20,0 \leq D_i \leq 10,0 \leq T_i \leq 500$；

对于$60% $的数据，$1 \leq n \leq 100,1 \leq m \leq 1,000,0 \leq k \leq 100,0 \leq D_i \leq 100,0 \leq T_i\leq 10,000$；

对于$100\%$的数据，$1 \leq n \leq 1,000,1 \leq m \leq 10,000 ,0 \leq k \leq 100,000,0 \leq D_i \leq 100 0 \leq T_i \leq 100,000$。

noip2011提高组day2第3题