风景迷人的小城 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
假设乘客上下车不需要时间。一个乘客的旅行时间,等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一辆观光车,有时候还要停下来等其他乘客,乘客们纷纷抱怨旅行时间太长了。于是聪明的司机 ZZ 给公交车安装了 k 个氮气加速器,每使用一个加速器,可以使其中一个 D_i-1。对于同一个 D_i 可以重复使用加速器,但是必须保证使用后 D_i\ge0。
那么 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 位乘客来到出发景点的时刻,出发的景点编号和到达的景点编号。
一个整数,表示最小的总旅行时间。
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。