HackerRank is starting a bus service in MountainView, California. The bus starts at time T = 0 at station1 and goes through station2, station3, station4 in that order and reaches the headquarters located at stationn. 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 stationi and stationj are 1000 meters apart, the bus takes 1000 seconds to travel from stationi to stationj.
The bus is equipped with K units of Nitro (N2O). If going from stationi to stationj 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 (N2O) present in the bus.
The second line contains n-1 space separated integers where the ith integer indicates the distance between station(i-1) to stationi.
m lines follow each containing 3 space separated integers. The ith line contains ti, si and ei in that order indicating the arrival time of the commuter at si at time ti with his destination being ei.
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 < di <= 100
0 <= ti <= 10000000
1 <= si < ei <= 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 1st and the 2nd commuter to arrive at station1 and travels to station2 carrying 2 passengers. The travel time from station1 to station2 is 1 second. It then waits for the 3rd commuter to board the bus at time = 5, 2nd commuter deboards the bus. The 3rd commuter boards the bus at t = 5. The bus now uses 2 units of nitro, this reduces the commute time to travel to station3 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 station1 to station2) + 2 (time spent waiting for commuter 3) + 2 (travel time from station2 to station3) = 6
- 1 (travel time from station1 to station2)
2 (travel time from station2 to station3)
6+1+2 = 9
hence the answer.
Timelimits
Timelimits for this challenge can be seen here