题目描述

风景迷人的小城 Y 市，拥有 $\red{n}$ 个美丽的景点。由于慕名而来的游客越来越多，Y 市特意安排了一辆观光公交车，为游客提供更便捷的交通服务。

观光公交车在第 $\red{0}$ 分钟出现在 $\red{1}$ 号景点，随后依次前往 $\red{2、3、4……n}$ 号景点。从第 $\red{i}$ 号景点开到第 $\red{i+1}$ 号景点需要 $\red{D_i}$ 分钟。任意时刻，公交车只能往前开，或在景点处等待。

设共有 $\red{m}$ 个游客，每位游客需要乘车 $\red{1}$ 次从一个景点到达另一个景点，第 $\red{i}$ 位游客在 $\red{T_i}$ 分钟来到景点 $\red{A_i}$，希望乘车前往景点 $\red{B_i}$（$\red{A_i<B_i}$）。为了使所有乘客都能顺利到达目的地，公交车在每站都必须等待需要从该景点出发的所有乘客都上车后才能出发开往下一景点。假设乘客上下车不需要时间。

一个乘客的旅行时间，等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一辆观光车，有时候还要停下来等其他乘客，乘客们纷纷抱怨旅行时间太长了。于是聪明的司机 ZZ 给公交车安装了 $\red{k}$ 个氮气加速器，每使用一个加速器，可以使其中一个 $\red{D_i}$ 减 $\red{1}$。对于同一个 $\red{D_i}$ 可以重复使用加速器，但是必须保证使用后 $\red{D_i\geq0}$。

那么 ZZ 该如何安排使用加速器，才能使所有乘客的旅行时间总和最小？

输入格式

输入文件名为 $\red{bus.in}$ 。

第 $\red{1}$ 行是 $\red{3}$ 个整数 $\red{n, m, k}$，每两个整数之间用一个空格隔开。分别表示景点数、乘客数和氮气加速器个数。

第 $\red{2}$ 行是 $\red{n-1}$ 个整数，每两个整数之间用一个空格隔开，第 $\red{i}$ 个数表示从第 $\red{i}$ 个景点开往第 $\red{i+1}$ 个景点所需要的时间，即 $\red{D_i}$ 。

第 $\red{3}$ 行至 $\red{m+2}$ 行每行 $\red{3}$ 个整数 $\red{T_i, A_i, B_i}$，每两个整数之间用一个空格隔开。第 $\red{i+2}$ 行表示第 $\red{i}$ 位乘客来到出发景点的时刻，出发的景点编号和到达的景点编号。

输出格式

输出文件名为 $\red{bus.out}$ 。

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

样例

样例输入

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

样例输出

10

样例说明

对 $\red{D_2}$ 使用 $\red{2}$ 个加速器，从 $\red{2}$ 号景点到 $\red{3}$ 号景点时间变为 $\red{2}$ 分钟。

公交车在第 $\red{1}$ 分钟从 $\red{1}$ 号景点出发，第 $\red{2}$ 分钟到达 $\red{2}$ 号景点，第 $\red{5}$ 分钟从 $\red{2}$ 号景点出发，

第 $\red{7}$ 分钟到达 $\red{3}$ 号景点。

第 $\red{1}$ 个旅客旅行时间 $\red{7-0 = 7}$ 分钟。

第 $\red{2}$ 个旅客旅行时间 $\red{2-1 = 1}$ 分钟。

第 $\red{3}$ 个旅客旅行时间 $\red{7-5 = 2}$ 分钟。

总时间 $\red{7+1+2 = 10}$ 分钟。

数据范围与提示

对于$\red{8\%}$ 的数据，$\red{k=0}$；

对于$\red{16\%}$ 的数据，$\red{k=1}$；

对于$\red{32\%}$ 的数据，$\red{2 \leq n \leq 50}$，$\red{m \leq 1,000}$，$\red{k \leq 20}$，$\red{D_i \leq 10}$，$\red{T_i \leq 500}$；

对于$\red{48\%}$ 的数据，$\red{n \leq 100}$，$\red{m \leq 1,000}$，$\red{k \leq 100}$，$\red{T_i \leq 10,000}$；

对于$\red{80\%}$ 的数据，$\red{n \leq 1,000}$，$\red{m \leq 10,000}$，$\red{k \leq 100,000}$，$\red{D_i \leq 100}$，$\red{T_i\leq 100,000}$；

对于$\red{100\%}$ 的数据，$\red{1 \leq n,m \leq 100,000}$，$\red{0 \leq k \leq 5,000,000}$，$\red{0 \leq D_i \leq 1,000}$，$\red{0 \leq T_i \leq 1,000,000}$。