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

Difficulty: HARD
Tags: Graph algorithms

Starter code:

Solutions:
import fileinput
input_list = []
for line in fileinput.input():
	temp_list6 = []
	temp_list6 = line.split(' ')
	temp_list6[len(temp_list6) - 1] = temp_list6[len(temp_list6) - 1].replace('\n', '')
	temp = []
	for i in temp_list6:
		if i.isdigit():
			temp.append(int(i))
	input_list.append(temp)
no_of_stations = input_list[0][0]
no_of_people = input_list[0][1]
nitro = input_list[0][2]
NoOfPassengersBwEachStation = [0] * no_of_stations
lastPersonArrival = [0] * (no_of_stations - 1)
destination_count = [0] * no_of_stations
for i in range(2, no_of_people + 2):
	index = input_list[i][2]
	destination_count[index - 1] += 1
for i in range(2, input_list[0][1] + 2):
	a = input_list[i][1]
	b = input_list[i][2]
	for j in range(a, b):
		NoOfPassengersBwEachStation[j] += 1
NoOfPassengersBwEachStation = NoOfPassengersBwEachStation[1:]
NoOfPassengersAfterEachStation = [0] * (no_of_stations - 1)
tempp = [0] * (no_of_stations - 1)
for i in range(-no_of_stations):
	for j in range(i + 1):
		NoOfPassengersAfterEachStation[i] += NoOfPassengersBwEachStation[j]
DistanceAfterEachStation = [0] * (no_of_stations - 1)
for i in range(no_of_stations - 1):
	for j in range(i + 1):
		DistanceAfterEachStation[i] += input_list[1][j]
lenght1 = len(NoOfPassengersBwEachStation)
weight = [0] * lenght1
for i in range(lenght1):
	weight[i] = input_list[1][i] * NoOfPassengersBwEachStation[i]
copy_weight = weight
copy_distance = input_list[1]
temp_new = []
for i in range(no_of_stations - 1):
	t = []
	t.append(copy_distance[i] * NoOfPassengersBwEachStation[i])
	t.append(NoOfPassengersBwEachStation[i])
	t.append(copy_distance[i])
	t.append(i)
	temp_new.append(t)
timeSpentByEverybodyAtAllStations = 0
for i in range(lenght1):
	timeSpentByEverybodyAtAllStations += input_list[1][i] * NoOfPassengersBwEachStation[i]
temp_input_list = []
temp_input_list = input_list[2:]
for i in range(no_of_people):
	temp = temp_input_list[i][0]
	temp_input_list[i][0] = temp_input_list[i][1]
	temp_input_list[i][1] = temp
temp_input_list.sort()
ArrivalTimeOfLastPersonAtTheStation = [0] * (no_of_stations + 1)
station_no = 1
for i in range(no_of_people):
	if station_no < temp_input_list[i][0]:
		ArrivalTimeOfLastPersonAtTheStation[station_no] = temp_input_list[i - 1][1]
		station_no = temp_input_list[i][0]
ArrivalTimeOfLastPersonAtTheStation[station_no] = temp_input_list[no_of_people - 1][1]
PossibleReachingTimeAtEachStation = [0] * no_of_stations
while nitro > 0:
	a = [0] * no_of_stations
	for i in range(1, no_of_stations):
		a[i] = a[i - 1] + input_list[1][i - 1]
	b = ArrivalTimeOfLastPersonAtTheStation[1:]
	for i in range(1, no_of_stations):
		b[i] = max(b[i - 1], b[i])
	c = [0] * (no_of_stations - 1)
	for i in range(no_of_stations - 1):
		c[i] = a[i + 1] - b[i + 1] - a[i] + b[i]
	c.append(0)
	d = []
	for i in range(no_of_stations):
		t = [0, 0, 1]
		t[0] = c[i]
		t[1] = i
		d.append(t)
	e = []
	for i in d:
		if i[0] <= 0:
			e.append(i)
	for i in e:
		d.remove(i)
	nitro_list = []
	for i in range(0, len(d) - 1):
		for j in range(i + 1, len(d)):
			if d[j][2] > 0:
				if d[i][1] + (j - i) == d[j][1]:
					d[i][2] += 1
					d[j][2] -= 1
	if d[len(d) - 1][2] > 0:
		if d[len(d) - 2][1] + 1 == d[len(d) - 1][1]:
			d[len(d) - 1][2] -= 1
	y = []
	for i in range(len(d)):
		if d[i][2] >= 1:
			t = [0, 0]
			for ii in range(d[i][2]):
				t[0] += destination_count[d[i][1] + ii + 1]
				t[1] = d[i][1]
				y.append(t)
	y.sort(reverse=True)
	temp_new.sort(reverse=True)
	index = y[0][1]
	copy_distance[index] -= 1
	nitro -= 1
	copy_weight[index] = copy_distance[index] * NoOfPassengersBwEachStation[index]
input_list[1] = copy_distance
TrainsArrivalTime = [0] * (no_of_stations + 1)
for i in range(2, no_of_stations + 1):
	TrainsArrivalTime[i] = max(TrainsArrivalTime[i - 1], ArrivalTimeOfLastPersonAtTheStation[i - 1]) + copy_distance[i - 2]
RequiredTime = 0
for i in range(no_of_people):
	RequiredTime += TrainsArrivalTime[temp_input_list[i][2]] - temp_input_list[i][1]
print(RequiredTime)