If the ship respects this timeline, and uses the afterburners perfectly timed, what is the minimum sum of travelling time for all the cargo ? The travelling time equals the time it arrived at the destination minus the time it boarded the ship.

Write a C++ program

The space shuttle USS Enterprise has to complete a tour between N planets, numbered from 1 to n, planet 1 being the start point, the Earth. The spaceship is transporting a very precious cargo, which cannot spend too much time in zero gravity, and has to be transported to the destination as soon as possible. At each planet, the ship has to wait for a specific amount of time, until all the cargo is loaded on the ship. In order to express distances between the planets in space, we define the Astronomical Unit (AU) : 1 AU = average distance from Earth to Sun. The ship is equipped with very advanced engines, and has a known speed of 1 AU / hour.

The ship is equipped with K units of solid afterburner fuel. If going from planet i to planet j takes x hours, then using t units of afterburner 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 afterburner can be used all at once or in multiples of 1 unit (you cannot use 0.5 units of afterburner fuel, since it is a solid fuel, not a liquid one)

If the ship respects this timeline, and uses the afterburners perfectly timed, what is the minimum sum of travelling time for all the cargo ? The travelling time equals the time it arrived at the destination minus the time it boarded the ship.

Remember that the ship must take all the cargo to its destination.

Input Format

a file called input.in :
The first line contains 3 space separated integers n, m and K which indicate the number of planets, total number of cargo that the ship needs to load and the total units of afterburner fuel present aboard the Enterprise.

The second line contains n-1 space separated integers where the i-th integer indicates the distance between planet (i-1) to planet i.

m lines follow each containing 3 space separated integers. The ith line contains ti, pi and ei in that order indicating the arrival time of the cargo at pi at time ti with his destination being ei.

nmK
d1 d2 ... dn-1 // di: the distance between planet_i to planet_(i+1).
t1 p1 e1 // cargo 1 arrives at his boarding point at p1 and his destination is e1 t2 p2 e2 // cargo 2 arrives at his boarding point at p2 and his destination is e2 ...
tm pm em

Constraints

0 < n <= 100000
0 < m <= 100000
0 <= K <= 10000000 0 < di <= 100
0 <= ti <= 10000000 1 <= si < ei <= n

Output Format

The minimal total travel time, written in the output.out file

Sample Input

332 14 113 212 523

Sample Output

9