观光公交

题目背景

感谢@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

输入输出格式

输入格式


第$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 ≤ n ≤ 50,1 ≤ m ≤ 1,000,0 ≤ k ≤ 20,0 ≤ D_i ≤ 10,0 ≤ T_i ≤ 500$; 对于$60\% $的数据,$1 ≤ n ≤ 100,1 ≤ m ≤ 1,000,0 ≤ k ≤ 100,0 ≤ D_i ≤ 100,0 ≤T_i≤ 10,000$; 对于$100\%$的数据,$1 ≤ n ≤ 1,000,1 ≤ m ≤ 10,000 ,0 ≤ k ≤ 100,000,0 ≤ D_i ≤ 100 0 ≤T_i ≤ 100,000$。 noip2011提高组day2第3题