# Drive

# Drive

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*in that order and reaches the headquarters located at

_{4}*station*. 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

_{n}*station*and

_{i}*station*are 1000 meters apart, the bus takes 1000 seconds to travel from

_{j}*station*to

_{i}*station*.

_{j}The bus is equipped with **K** units of Nitro (N_{2}O). If going from *station _{i}* to

*station*takes

_{j}*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