题目背景

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

题目描述

风景迷人的小城 Y 市，拥有 $n$ 个美丽的景点。由于慕名而来的游客越来越多，Y 市特意安排了一辆观光公交车，为游客提供更便捷的交通服务。观光公交车在第 $0$ 分钟出现在 $1$ 号景点，随后依次前往 $2,3,4,\cdots,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$ 位乘客来到出发景点的时刻，出发的景点编号和到达的景点编号。

输出格式

一个整数，表示最小的总旅行时间。

3 3 2
1 4
0 1 3
1 1 2
5 2 3

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 \le n \le 50$，$1 \le m \le 10^3$，$0 \le k \le 20$，$0 \le D_i \le 10$，$0 \le T_i \le 500$。

对于 $60\%$ 的数据，$1 \le n \le 100$，$1 \le m \le 10^3$，$0 \le k \le 100$，$0 \le D_i \le 100$，$0 \le T_i \le 10^4$。

对于 $100\%$ 的数据，$1 \le n \le 10^3$，$1 \le m \le 10^4$，$0 \le k \le 10^5$，$0 \le D_i \le 100$，$0 \le T_i \le 10^5$。