题目描述

风景迷人的小城 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<B_i$）。为了使所有乘客都能顺利到达目的地，公交车在每站都必须等待需要从该景点出发的所有乘客都上车后才能出发开往下一景点。

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

输出格式

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

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

10

提示