某个公交车线路有 N 个站点（但只有1辆车），从第 i 个站点到第 i+1 个站点需要 D[i] 单位时间。现在有 M 名旅客需要搭乘公交车，每位旅客于 T[i] 时间到达 A[i] 车站，并搭乘公交车前往 B[i] 车站。 由于顾客是上帝，所以公交车会等待在该站点上车的所有旅客都上车，然后才继续出发。旅客们都抱怨等待时间（每位旅客到达车站的时间 T[i] 直到旅客到站下车的时间）太长。为了使等待时间缩短，公交车上配备了 K 颗加速器。每使用一个加速器，可以使 D[i] 缩短 1 个单位时间，但前提是D[i]>=0。求在合理使用加速器的情况下，所有旅客等待的总时间的最小值。

输入第一行是三个整数 N,M,K 。

第二行含 N-1 个整数，每个整数表示 i 站到 i+1 站所需要的时间 D[i] 。

之后的 M 行每行是一个旅客的到达站点时间 T[i] ，出发站点 A[i] ，目标站点 B[i]。

输出所有旅客等待的总时间的最小值。