HackerRank is starting a bus service in MountainView, California. The bus starts at time T = 0 at $station_{1}$and goes through $station_{2}$, $station_{3}$, $station_{4}$ in that order and reaches the headquarters located at $station_{n}$. At every station, the bus waits for various commuters to arrive before it departs to the next station. Ignoring the acceleration, the bus moves at 1 meter / second. i.e., if $station_{i}$ and $station_{j}$ are 1000 meters apart, the bus takes 1000 seconds to travel from $station_{i}$ to $station_{j}$.

The bus is equipped with K units of Nitro ($N_{2}$O). If going from $station_{i}$ to $station_{j}$ takes x seconds, then using t units of nitro can decrease the time taken to max(x-t, 0) seconds where max(a,b) denotes the greater of the two values between a & b. The Nitro can be used all at once or in multiples of 1 unit.

If the bus driver travels optimally, what is the minimum sum of travelling time for all commuters? The travelling time equals to the time he/she arrived at the destination minus the time he/she arrived the start station.

Please remember that the driver must take all passengers to their destination.

Input Format

The first line contains 3 space separated integers n, m and K which indicate the number of stations, total number of people who board the bus at various stations and the total units of Nitro ($N_{2}$O) present in the bus.

The second line contains n-1 space separated integers where the$ i^{th}$ integer indicates the distance between $station_{(i-1)}$ to $station_{i}$.

m lines follow each containing 3 space separated integers. The $ i^{th}$ line contains $t_{i}$, $s_{i}$ and $e_{i}$ in that order indicating the arrival time of the commuter at $s_{i}$ at time $t_{i}$ with his destination being $e_{i}$.

n m K
d1 d2 ... dn-1 // di: the distance between station_i to station_(i+1).
t1 s1 e1 // commuter 1 arrives at his boarding point at s1 and his destination is e1
t2 s2 e2
...
tm sm em

Constraints

0 < n <= 100000

0 < m <= 100000

0 <= K <= 10000000

0 < $d_{i}$ <= 100

0 <= $t_{i}$ <= 10000000

1 <= $s_{i}$ < $e_{i}$ <= n

Output Format

The minimal total travel time.

Sample Input
3 3 2
1 4
1 1 3
2 1 2
5 2 3

Sample Output
9

Explanation

The bus waits for the $1^{st}$ and the $2^{nd}$ commuter to arrive at $station_{1}$ and travels to $station_{2}$ carrying 2 passengers. The travel time from $station_{1}$ to $station_{2}$ is 1 second. It then waits for the $3^{rd}$ commuter to board the bus at time = 5, $2^{nd}$ commuter deboards the bus. The $3^{rd}$ commuter boards the bus at t = 5. The bus now uses 2 units of nitro, this reduces the commute time to travel to $station_{3}$ from 4 to 2.

Hence, the total time spent by each of the passengers on the bus is

1 (time spent waiting for commuter 2) + 1 (travel time from $station_{1}$ to $station_{2}$) + 2 (time spent waiting for commuter 3) + 2 (travel time from $station_{2}$ to $station_{3}$) = 6
1 (travel time from $station_{1}$ to $station_{2}$)

2 (travel time from $station_{2}$ to $station_{3}$)

6+1+2 = 9

hence the answer.

Timelimits

Timelimits for this challenge can be seen here

见题面

见题面