4049: 【11NOIP提高组】观光公交
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
风景迷人的小城Y市，拥有$n$个美丽的景点。由于慕名而来的游客越来越多，Y市特意安排了一辆观光公交车，为游客提供更便捷的交通服务。观光公交车在第0分钟出现在$1$号景点，随后依次前往$2、3、4……n$ 号景点。从第$i$ 号景点开到第$i+1$ 号景点需要$D_i$ 分钟。任意时刻，公交车只能往前开，或在景点处等待。n设共有$m$个游客，每位游客需要乘车$1$次从一个景点到达另一个景点，第i位游客在$T_i$分钟来到景点$A_i$，希望乘车前往景点$B_i(A_i
Input
第 $1$ 行是$3$ 个整数$n, m, k$，每两个整数之间用一个空格隔开。分别表示景点数、乘客数和氮气加速器个数。n第 $2$ 行是$n-1$ 个整数，每两个整数之间用一个空格隔开，第$i$ 个数表示从第$i$ 个景点开往第$i+1$ 个景点所需要的时间，即$D_i$。n第 $3$ 行至$m+2$ 行每行$3$ 个整数$T_i, A_i, B_i$，每两个整数之间用一个空格隔开。第$i+2$ 行表示第$i$ 位乘客来到出发景点的时，出发的景点编号和到达的景点编号。
Output
共一行，包含一个整数，表示最小的总旅行时间。
Sample Input Copy
3 3 2
1 4
0 1 3
1 1 2
5 2 3Sample Output Copy
10