priorityQuest

from queue import PriorityQueue

# Function to calculate the minimum cost
# required to reach the end of line

def minCost(N, K, M, a, b):
	flag = 1
	d = {}

	# store index of the station and its respective
	# rate of fuel

	for i in range(M):
		d[a[i]] = b[i]

		"""
		Two condition to check:

		1. If last station is far away such that it cannot
		be reached even if full capacity is filled

		2. if ith station is far away such that it cannot be reached
		even if full capacity is filled (this is done by checking
		if the difference of two adjacent element exceeds k)
		"""

		if K < N-a[i] and i == M-1:
			flag = 0
			break

		if i < M-1 and K < a[i+1] - a[i]:
			flag = 0
			break

	if not flag:
		print(-1)
		return;



	# store station index and cost of fuel and
	# litres of petrol which is being fueled

	pq=PriorityQueue()
	cost = 0
	flag = 0

	for i in range(N):
		# check if station is at current index
		if i in d: pq.put([i, d[i], 0])

 		# remove all stations where fuel cannot be pumped
		print(pq.queue[-1])
		while not pq.empty() and pq.queue[-1][2]==K: pq.get()
		# # if no station left to fill fuel
		# not possible to reach end
		if pq.empty():
			flag = 1
			break

		# store best station visited so far
		# bestStation = pq.queue[-1]
		bestStation = pq.get()

		cost += bestStation[1]

		bestStation[2] += 1

		pq.put(bestStation)

		if flag:
			print(-1)
			return;

	print(cost)




# Driver code
if __name__ == "__main__":
	"""
	Test case 1:
	N = 10
	K = 3
	M = 4

	a = [0, 1, 4, 6]
	b = [5, 2, 2, 4]

	output: -1
	"""

	"""
	Test case 2:
	N = 10
	K = 10
	M = 2

	a = [0, 1]
	b = [5, 2]

	output: 23
	"""



	N = 10
	K = 5
	M = 3

	a = [0, 3, 5]
	b = [5, 9, 3]

	minCost(N, K, M, a, b)