A29956.观光公交（Day 2）

风景迷人的小城Y市，拥有n个美丽的景点。由于慕名而来的游客越来越多，Y市特意安排了一辆观光公交车，为游客提供更便捷的交通服务。观光公交车在第0分钟出现在1号景点，随后依次前往2、3、4...n号景点。从第i号景点开到第i+1号景点需要Di分钟。任意时刻，公交车只能往前开，或在景点处等待。

设共有m个游客，每位游客需要乘车1次从一个景点到达另一个景点，第i位游客在Ti分钟来到景点Ai，希望乘车前往景点Bi（Ai <Bi ）。为了使所有乘客都能顺利到达目的地，公交车在每站都必须等待需要从该景点出发的所有

每组输入数据的第1行是3个整数n, m, k，每两个整数之间用一个空格隔开。分别表示景点数、乘客数和氮气加速器个数。

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

第3行至m+2行每行3个整数Ti, Ai, Bi，每两个整数之间用一个空格隔开。第i+2行表示第i位乘客来到出发景点的时刻，出发的景点编号和到达的景点编号。





数据规模：


对于10%的数据，k=0；


对于20%的数据，k=1；


对于40%

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

下面是对样例数据的解释：


对D2使用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分钟。