Optimized Tourist Bus Scheduling

City Y is famous for its beautiful attractions. The city has n scenic spots numbered 1 through n. At time 0 the sightseeing bus appears at spot 1 and then proceeds to spots 2, 3, …, n in order. The travel time from spot i to spot i+1 is given by \(D_i\) minutes. At any time the bus may only move forward or wait at a spot.

There are m tourists. Each tourist takes the bus exactly once – boarding at spot \(A_i\) and riding to spot \(B_i\) (with \(A_i < B_i\)). The i-th tourist arrives at their boarding spot at time \(T_i\). In order for every passenger to reach their destination, the bus must not leave a spot until all tourists waiting at that spot (i.e. those who have arrived by that time) have boarded. (Assume that getting on and off the bus takes no time.)

A tourist’s travel time is the difference between the time the bus arrives at his destination and \(T_i\). Complaints arose that the travel times were too long because sometimes the bus needed to wait. To improve the service, the clever driver ZZ installs \(k\) nitro boosters. Using one nitro booster on a travel segment reduces the corresponding \(D_i\) by 1 minute (and multiple boosters can be used on the same segment, but \(D_i\) must remain nonnegative).

Determine how to use the \(k\) boosters in order to minimize the total travel time of all the passengers.

Note: Boosters used on a segment may reduce the bus travel time, but if the bus would otherwise have to wait at the next spot for passengers arriving later, then an earlier arrival does not improve (or may even be completely absorbed by) the waiting time. It is therefore optimal to apply boosters only when they actually reduce the final arrival times of passengers.

Hint: You may simulate the bus route. Let \(a_1=0\) and for \(i=1,2,\dots,n-1\) let the waiting threshold at spot \(i\) be \(L_i = \max\{T_j: A_j=i\}\) (and define \(L_i=0\) if no passenger starts at \(i\)). Then the bus arrival time is computed as:

[ a_{i+1} = \max{a_i, L_i} + (D_i - b_i), ,\quad 1 \le i \le n-1, ]

where \(b_i\) is the number of boosters used on segment \(i\) (with \(0 \le b_i \le D_i\)) and \(\sum_{i=1}^{n-1} b_i \le k\). The total cost to minimize is \(\sum_{\text{tourist } i}\bigl(a_{B_i} - T_i\bigr).\)

inputFormat

The first line contains three integers \(n\), \(m\) and \(k\) (number of spots, number of tourists, and number of boosters).

The second line contains \(n-1\) integers: \(D_1, D_2, \dots, D_{n-1}\) (the travel times between consecutive spots).

The following \(m\) lines each contain three integers: \(A_i\), \(B_i\) and \(T_i\) (the boarding spot, the destination spot, and the arrival time at the boarding spot) for the \(i\)-th tourist.

outputFormat

Output a single integer, the minimum possible total travel time of all passengers, i.e. \(\sum_{i=1}^{m} (a_{B_i} - T_i)\), after using at most \(k\) boosters optimally.

sample

3 1 1
10 10
1 3 5

19