Tieu owns a pizza restaurant and he manages it in his own way.  While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes. 

Different kinds of pizzas take different amounts of time to cook. Also, once he starts cooking a pizza, he cannot cook another pizza until the first pizza is completely cooked. Let's say we have three customers who come at time t=0, t=1, & t=2 respectively, and the time needed to cook their pizzas is 3, 9, & 6 respectively. If Tieu applies first-come, first-served rule, then the waiting time of three customers is 3, 11, & 16  respectively. The average waiting time in this case is (3 + 11 + 16) / 3 = 10. This is not an optimized solution. After serving the first customer at time t=3, Tieu can choose to serve the third customer. In that case, the waiting time will be 3, 7, & 17 respectively. Hence the average waiting time is (3 + 7 + 17) / 3 = 9.

Help Tieu achieve the minimum average waiting time. For the sake of simplicity, just find the integer part of the minimum average waiting time.

Input Format

The first line contains an integer N, which is the number of customers. 

In the next N lines, the i^{th} line contains two space separated numbers T_{i} and L_{i}. T_{i} is the time when i^{th} customer order a pizza, and L_{i} is the time required to cook that pizza.  

The $i^{\mbox{th}}$ customer is not the customer arriving at the $i^{\mbox{th}}$ arrival time. 

Output Format

Display the integer part of the minimum average waiting time.

Constraints

1 ≤ N ≤ $10^{5}$
0 ≤ T_{i} ≤ $10^{9}$
1 ≤ L_{i} ≤$10^{9}$

Note

The waiting time is calculated as the difference between the time a customer orders pizza (the time at which they enter the shop) and the time she is served.

Cook does not know about the future orders.

Sample Input #00

3
0 3
1 9
2 6

Sample Output #00

9

Sample Input #01

3
0 3
1 9
2 5

Sample Output #01

8

Explanation #01

Let's call the person ordering at time = 0 as A, time = 1 as B and time = 2 as C. By delivering pizza for A, C and B we get the minimum average wait time to be 

(3 + 6 + 16)/3 = 25/3 = 8.33 

the integer part is 8 and hence the answer.

Difficulty: MEDIUM_HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
import heapq
N = int(input())
Tasks = [tuple((int(_) for _ in input().split())) for _ in range(N)]
Tasks.sort()
TotalWaiting = 0
currentTime = 0
currentWaiting = []
i = 0
while i < len(Tasks):
	if not currentWaiting and Tasks[i][0] > currentTime:
		currentTime = Tasks[i][0]
	while i < len(Tasks) and Tasks[i][0] <= currentTime:
		heapq.heappush(currentWaiting, tuple([Tasks[i][1], Tasks[i][0]]))
		i += 1
	task = heapq.heappop(currentWaiting)
	currentTime += task[0]
	TotalWaiting += currentTime - task[1]
	if i >= len(Tasks):
		while currentWaiting:
			task = heapq.heappop(currentWaiting)
			currentTime += task[0]
			TotalWaiting += currentTime - task[1]
print(TotalWaiting // N)


import sys
import heapq
import collections
Order = collections.namedtuple('Order', ['arrival_time', 'cook_time'])

class OrderHeap(object):

	def __init__(self):
		self._data = []

	def push(self, order):
		heapq.heappush(self._data, (order.cook_time, order))

	def pop(self):
		return heapq.heappop(self._data)[1]

	def empty(self):
		return not bool(len(self._data))
N = int(sys.stdin.readline())
orders = []
for _ in range(N):
	t = tuple((int(x) for x in sys.stdin.readline().split()))
	orders.append(Order(arrival_time=t[0], cook_time=t[1]))
orders.sort(key=lambda x: x.arrival_time)
orders = collections.deque(orders)
pending = OrderHeap()
current_time = 0
total_wait_time = 0
while 1:
	while orders and current_time >= orders[0].arrival_time:
		pending.push(orders.popleft())
	if not pending.empty():
		o = pending.pop()
		current_time += o.cook_time
		total_wait_time += current_time - o.arrival_time
	elif len(orders):
		current_time = orders[0].arrival_time
	else:
		break
avg = int(total_wait_time / N)
print(avg)


import queue
pre_orders = []
last_order = None
cases = int(input())
available = queue.PriorityQueue(cases)
total_wait = 0
for _ in range(cases):
	pre_orders.append([int(x) for x in input().split()])
pre_orders.sort(key=lambda x: x[0], reverse=True)
last_order = pre_orders.pop()
last_order.append(last_order[0] + last_order[1])
total_wait += last_order[2] - last_order[0]
time = last_order[2]
for _ in range(cases - 1):
	while pre_orders and time >= pre_orders[-1][0]:
		node = pre_orders.pop()
		available.put((node[1], node))
	if available:
		deleted = available.get()[1]
		deleted.append(time + deleted[1])
		total_wait += deleted[2] - deleted[0]
		last_order = deleted
	else:
		temp = pre_orders.pop()
		temp.append(temp[0] + temp[1])
		total_wait += temp[2] - temp[0]
		last_order = temp
	time = last_order[2]
print(int(total_wait / cases))


from heapq import heappush, heappop
n = int(input())
tl = []
for _ in range(n):
	tl.append(list(map(int, input().split())))
tl.sort()
(ts, t, i) = (0, 0, 0)
hp = []
while i < len(tl) or len(hp) > 0:
	if len(hp) == 0 and t < tl[i][0]:
		t = tl[0][0]
	while i < len(tl) and tl[i][0] <= t:
		heappush(hp, (tl[i][1], tl[i][0]))
		i += 1
	(lx, tx) = hp[0]
	heappop(hp)
	t += lx
	ts += t - tx
print(int(ts / n))


import heapq, sys
N = int(sys.stdin.readline())
X = sorted((list(map(int, sys.stdin.readline().split())) for _ in range(N)))
time = 0
total_time = 0
queue = []
while X or queue:
	while X and (not queue or X[0][0] <= time):
		(T, L) = X.pop(0)
		heapq.heappush(queue, (L, T))
		time = max(time, T)
	(L, T) = heapq.heappop(queue)
	time += L
	total_time += time - T
print(total_time // N)


import heapq, sys
N = int(sys.stdin.readline())
X = sorted((list(map(int, sys.stdin.readline().split())) for _ in range(N)))
time = 0
total_time = 0
queue = []
while X or queue:
	while X and (not queue or X[0][0] <= time):
		(T, L) = X.pop(0)
		heapq.heappush(queue, (L, T))
		time = max(time, T)
	(L, T) = heapq.heappop(queue)
	time += L
	total_time += time - T
print(total_time // N)


__author__ = 'aditya.patel'
import heapq
from operator import attrgetter

class Process:

	def __init__(self, a, b):
		self.at = a
		self.ct = b

	def __lt__(self, other):
		return self.ct < other.ct
q = []
pr_q = []
All_Process = []
ini_pr = 0
N = int(input())
for i in range(N):
	(a, b) = map(int, input().split(' '))
	Individual = Process(a, b)
	q.append(Individual)
tot = 0
p_on = 0
q = sorted(q, key=lambda q: q.at)
itera = 0
heapq.heappush(pr_q, q[itera])
itera += 1
cur_process = []
for i in range(len(q)):
	cur_process = heapq.heappop(pr_q)
	if cur_process.at > p_on:
		tot += cur_process.ct
		p_on += cur_process.ct + cur_process.at
	else:
		tot += p_on + cur_process.ct - cur_process.at
		p_on += cur_process.ct
	while itera < len(q) and p_on > q[itera].at:
		heapq.heappush(pr_q, q[itera])
		itera += 1
	if itera < len(q) and len(pr_q) is None:
		heapq.heappush(pr_q, q[itera])
		itera += 1
print(tot // len(q))


import heapq, sys
N = int(sys.stdin.readline())
X = sorted((list(map(int, sys.stdin.readline().split())) for _ in range(N)))
time = 0
total_time = 0
queue = []
while X or queue:
	while X and (not queue or X[0][0] <= time):
		(T, L) = X.pop(0)
		heapq.heappush(queue, (L, T))
		time = max(time, T)
	(L, T) = heapq.heappop(queue)
	time += L
	total_time += time - T
print(total_time // N)


import heapq, sys
N = int(sys.stdin.readline())
X = sorted((list(map(int, sys.stdin.readline().split())) for _ in range(N)))
time = 0
total_time = 0
queue = []
while X or queue:
	while X and (not queue or X[0][0] <= time):
		(T, L) = X.pop(0)
		heapq.heappush(queue, (L, T))
		time = max(time, T)
	(L, T) = heapq.heappop(queue)
	time += L
	total_time += time - T
print(total_time // N)


import heapq
N = int(input())
Tasks = [tuple((int(_) for _ in input().split())) for _ in range(N)]
Tasks.sort()
TotalWaiting = 0
currentTime = 0
currentWaiting = []
i = 0
while i < len(Tasks):
	if not currentWaiting and Tasks[i][0] > currentTime:
		currentTime = Tasks[i][0]
	while i < len(Tasks) and Tasks[i][0] <= currentTime:
		heapq.heappush(currentWaiting, tuple([Tasks[i][1], Tasks[i][0]]))
		i += 1
	task = heapq.heappop(currentWaiting)
	currentTime += task[0]
	TotalWaiting += currentTime - task[1]
while currentWaiting:
	task = heapq.heappop(currentWaiting)
	currentTime += task[0]
	TotalWaiting += currentTime - task[1]
print(TotalWaiting // N)


import heapq, math
from heapq import heappush
from heapq import heappop
N = int(input())
heapIn = []
for n in range(0, N):
	(T, L) = [int(x) for x in input().strip().split(' ')]
	heappush(heapIn, (T, L))
heapWait = []
(curT, curL) = heappop(heapIn)
t = curT + curL
allWait = curL
while len(heapIn) > 0:
	while len(heapIn) > 0 and t > heapIn[0][0]:
		(T, L) = heappop(heapIn)
		heappush(heapWait, (L, T))
	if len(heapWait) > 0:
		(curL, curT) = heappop(heapWait)
		t += curL
		allWait += t - curT
	else:
		(curT, curL) = heappop(heapIn)
		t = curT + curL
		allWait += t - curT
while len(heapWait) > 0:
	(curL, curT) = heappop(heapWait)
	t += curL
	allWait += t - curT
print(math.floor(allWait / N))


import heapq
n = int(input())
orders = []
for i in range(n):
	orders.append(list(map(int, input().strip().split(' '))))
orders = sorted(orders)
i = 0
q = []
total_wait = 0
current_time = orders[0][0]
while i < n or q:
	while i < n and orders[i][0] <= current_time:
		o = orders[i]
		heapq.heappush(q, (o[1], o[0]))
		i += 1
	if not q:
		i += 1
		current_time = orders[i][1]
		continue
	o = heapq.heappop(q)
	current_time += o[0]
	total_wait += current_time - o[1]
print(total_wait // n)


import heapq
N = int(input())
P = []
for i in range(N):
	heapq.heappush(P, tuple([int(x) for x in input().split()]))
timer = P[0][0]
nextJob = P[0][0] + P[0][1]
end = False
heap = []
curr = (P[0][0], P[0][1])
total = 0
heapq.heappop(P)
while not end:
	if P:
		timer = min(P[0][0], nextJob)
	else:
		timer = nextJob
	if P and P[0][0] == timer:
		heapq.heappush(heap, (P[0][1], P[0][0]))
		heapq.heappop(P)
	if timer == nextJob:
		if heap:
			wt = timer - curr[1] - curr[0]
			tat = wt + curr[1]
			total += tat
			pizza = heapq.heappop(heap)
			nextJob += pizza[0]
			curr = (pizza[1], pizza[0])
	if not P and (not heap) and (timer == nextJob):
		wt = timer - curr[1] - curr[0]
		tat = wt + curr[1]
		total += tat
		end = True
print(int(total / N))


import heapq, sys
N = int(sys.stdin.readline())
X = sorted((list(map(int, sys.stdin.readline().split())) for _ in range(N)))
time = 0
total_time = 0
queue = []
while X or queue:
	while X and (not queue or X[0][0] <= time):
		(T, L) = X.pop(0)
		heapq.heappush(queue, (L, T))
		time = max(time, T)
	(L, T) = heapq.heappop(queue)
	time += L
	total_time += time - T
print(total_time // N)


from heapq import heappush, heappop
n = int(input())
cust = []
for i in range(n):
	(ti, ci) = map(int, input().split(' '))
	cust.append([ci, ti])
heap = []
T = 1
C = 0
cust.sort(key=lambda t: t[T])
curtime = 0
wait = 0
count = 0
while count < n:
	while len(cust) > 0 and cust[0][T] <= curtime:
		heappush(heap, cust.pop(0))
	if len(heap) == 0:
		curtime = cust[0][T]
		continue
	cur = heappop(heap)
	curtime += cur[C]
	wait += curtime - cur[T]
	count += 1
print(wait // n)


import heapq, sys
N = int(sys.stdin.readline())
X = sorted((list(map(int, sys.stdin.readline().split())) for _ in range(N)))
time = 0
total_time = 0
queue = []
while X or queue:
	while X and (not queue or X[0][0] <= time):
		(T, L) = X.pop(0)
		heapq.heappush(queue, (L, T))
		time = max(time, T)
	(L, T) = heapq.heappop(queue)
	time += L
	total_time += time - T
print(total_time // N)


import heapq
import operator
num_pizzas = int(input())
time_left_in_oven = 0
current_time = 0
heap = []
pizzas = []
for _ in range(num_pizzas):
	pizzas.append(tuple([int(x) for x in input().split()]))
pizzas.sort(key=operator.itemgetter(0))

class Pizza:

	def __init__(self, current_time, starting_time, cooking_time):
		self.current_time = current_time
		self.starting_time = starting_time
		self.cooking_time = cooking_time

	def __lt__(self, other):
		return self.cooking_time < other.cooking_time
current_time = pizzas[0][0]
customer_waiting_times = []
while len(pizzas) > 0 or len(heap) > 0:
	pizzas_to_cook = [pizza for pizza in pizzas if pizza[0] <= current_time]
	pizzas = pizzas[len(pizzas_to_cook):]
	for (time, cooking_time) in pizzas_to_cook:
		heapq.heappush(heap, Pizza(current_time, time, cooking_time))
	pizza = heapq.heappop(heap)
	customer_waiting_times.append(current_time - pizza.starting_time + pizza.cooking_time)
	current_time = current_time + pizza.cooking_time
print(sum(customer_waiting_times) // len(customer_waiting_times))


import heapq, sys
N = int(sys.stdin.readline())
X = sorted((list(map(int, sys.stdin.readline().split())) for _ in range(N)))
time = 0
total_time = 0
queue = []
while X or queue:
	while X and (not queue or X[0][0] <= time):
		(T, L) = X.pop(0)
		heapq.heappush(queue, (L, T))
		time = max(time, T)
	(L, T) = heapq.heappop(queue)
	time += L
	total_time += time - T
print(total_time // N)


from heapq import *

def heapify_max(heap):
	for i in range(len(heap)):
		heap[i] = -heap[i]
	heapify(heap)

def heappeek(heap):
	x = heappop(heap)
	heappush(heap, x)
	return x
n = int(input())
arrival_pq = []
cooking_pq = []
for i in range(n):
	(arr, cook) = map(int, input().split())
	heappush(arrival_pq, (arr, cook))
total_time = 0
t = 0
while len(arrival_pq) > 0:
	while len(arrival_pq) > 0 and heappeek(arrival_pq)[0] <= t:
		(arr, cook) = heappop(arrival_pq)
		heappush(cooking_pq, (cook, arr))
	if len(cooking_pq) > 0:
		(cook, arr) = heappop(cooking_pq)
		t += cook
		total_time += t - arr
	elif len(arrival_pq) > 0:
		t = heappeek(arrival_pq)[0]
	else:
		break
while len(cooking_pq) > 0:
	(cook, arr) = heappop(cooking_pq)
	t += cook
	total_time += t - arr
print(total_time // n)


import heapq
N = int(input())
orders = []
for i in range(N):
	details = input().split()
	orders.append([int(details[0]), int(details[1])])
orders.sort(key=lambda order: order[0])
current_time = 0
time_waited = 0
acc_orders = []
while orders:
	next_order = orders.pop(0)
	while current_time <= next_order[0] and acc_orders:
		order_time = heapq.heappop(acc_orders)
		time_waited += (len(acc_orders) + 1) * order_time
		current_time += order_time
	if current_time < next_order[0]:
		current_time = next_order[0]
	heapq.heappush(acc_orders, next_order[1])
	if current_time > next_order[0]:
		time_waited += current_time - next_order[0]
while acc_orders:
	order_time = heapq.heappop(acc_orders)
	time_waited += (len(acc_orders) + 1) * order_time
print(time_waited // N)


from heapq import *
customers = []
size = int(input())
h = []
track = {}
nextFree = 0
sum = 0
pizzasServed = 0
cycleStart = 0
prevSum = 0
for i in range(size):
	(arrival, cookingTime) = map(int, input().split())
	heappush(customers, (arrival, cookingTime))
while len(customers):
	(arrival, cookingTime) = heappop(customers)
	if arrival <= nextFree:
		heappush(h, (cookingTime, arrival))
		continue
	elif len(h):
		(nextPersonPizzaTime, arrivalTime) = heappop(h)
		sum += nextPersonPizzaTime + nextFree - arrivalTime
		nextFree += nextPersonPizzaTime
		heappush(h, (cookingTime, arrival))
	else:
		sum += cookingTime
		nextFree = max(nextFree, arrival)
		nextFree += cookingTime
while len(h):
	(nextPersonPizzaTime, arrivalTime) = heappop(h)
	nextFree = max(nextFree, arrivalTime)
	sum += nextPersonPizzaTime + nextFree - arrivalTime
	nextFree += nextPersonPizzaTime
print(int(sum / size))


from heapq import heappush, heappop
n = int(input())
customers = []
orders = []
for _ in range(n):
	(t, l) = map(int, input().split())
	heappush(customers, (t, l))
ct = 0
waiting_time = 0
while customers or orders:
	if not orders or (customers and customers[0][0] <= ct):
		if not orders:
			ct = max(customers[0][0], ct)
		while customers and customers[0][0] <= ct:
			(t, l) = heappop(customers)
			heappush(orders, (l, t))
	(l, t) = heappop(orders)
	ct += l
	waiting_time += ct - t
print(waiting_time // n)


from heapq import heappush, heappop
customers = []
N = int(input())
for i in range(N):
	(T, L) = tuple([int(x) for x in input().split()])
	customers.append((L, T, i))
waiting_time = dict()
total_time = 0
customers = sorted(customers, key=lambda x: x[1])
customer_heap = []
for i in range(N):
	(curr_total_time, curr_start_time, curr_customer_id) = customers[i]
	while total_time < curr_start_time and customer_heap:
		customer = heappop(customer_heap)
		(time_duration, start_time, ordinal_id) = customer
		if True or total_time + time_duration <= curr_start_time:
			total_time = max(start_time, total_time) + time_duration
			waiting_time[customer] = total_time - start_time
		else:
			time_duration -= curr_start_time - total_time
			customer = (time_duration, start_time, ordinal_id)
			heappush(customer_heap, customer)
			total_time = curr_start_time
	heappush(customer_heap, customers[i])
while customer_heap:
	customer = heappop(customer_heap)
	(time_duration, start_time, ordinal_id) = customer
	total_time += time_duration
	waiting_time[customer] = total_time - start_time
print(int(sum(waiting_time.values()) / len(waiting_time)))


import sys
testCases = int(sys.stdin.readline())
lines = sys.stdin.readlines()
cookTimes = []
minTime = float('inf')
for line in lines:
	line = line.split(' ')
	t = int(line[0])
	cookTime = int(line[1])
	cookTimes.append((cookTime, t))
	if t < minTime:
		minTime = t
cookTimes.sort()
currentT = minTime
totalWait = 0
while True:
	if len(cookTimes) == 0:
		break
	else:
		popped = None
		for time in cookTimes:
			if time[1] <= currentT:
				popped = time
				cookTimes.remove(popped)
				break
		if popped:
			currentT = currentT + popped[0]
			totalWait = totalWait + currentT - popped[1]
		else:
			currentT = currentT + 1
print(int(totalWait / testCases))


import heapq, sys
N = int(sys.stdin.readline())
X = sorted((list(map(int, sys.stdin.readline().split())) for _ in range(N)))
time = 0
total_time = 0
queue = []
while X or queue:
	while X and (not queue or X[0][0] <= time):
		(T, L) = X.pop(0)
		heapq.heappush(queue, (L, T))
		time = max(time, T)
	(L, T) = heapq.heappop(queue)
	time += L
	total_time += time - T
print(total_time // N)


import heapq
ct = 0
allc = []
wt = []
for _ in range(int(input())):
	heapq.heappush(allc, tuple(map(int, input().split())))
while len(allc):
	intimec = [heapq.heappop(allc)]
	while len(allc) and allc[0][0] == intimec[0][0]:
		intimec.append(heapq.heappop(allc))
	intimec = [(a[1], a[0]) for a in intimec]
	heapq.heapify(intimec)
	ct = max(ct, intimec[0][1])
	while len(intimec):
		cc = heapq.heappop(intimec)
		wt.append(cc[0] + (ct - cc[1]))
		ct += cc[0]
		while len(allc) and allc[0][0] <= ct:
			c = heapq.heappop(allc)
			heapq.heappush(intimec, (c[1], c[0]))
print(int(sum(wt) / len(wt)))


from heapq import *
N = int(input().strip())
A = []
for i in range(N):
	(t, l) = list(map(int, input().strip().split(' ')))
	A.append((t, l))
A.sort(key=lambda x: x[0], reverse=True)
B = []
total_time = 0
tot_wait_time = 0
i = len(A) - 1
while i >= 0:
	if not B:
		(t, l) = A[i]
		total_time = t + l
		tot_wait_time += l
		i -= 1
		if i < 0:
			break
	else:
		x = heappop(B)
		(l, t) = (x[0], x[1])
		total_time += l
		tot_wait_time += total_time - t
	while i >= 0:
		x = A[i]
		(t, l) = (x[0], x[1])
		if t <= total_time:
			heappush(B, (l, t))
			i -= 1
		else:
			break
while B:
	x = heappop(B)
	(l, t) = (x[0], x[1])
	total_time += l
	tot_wait_time += total_time - t
avg_wait_time = int(tot_wait_time / N)
print(avg_wait_time)


import heapq

def totalwait(pairs):
	pairs = sorted(pairs)
	pairq = []
	t = 0
	wait = 0
	i = 0
	while pairq or i < len(pairs):
		while i < len(pairs) and t >= pairs[i][0]:
			heapq.heappush(pairq, pairs[i][1])
			wait -= pairs[i][0]
			i += 1
		if pairq:
			t += heapq.heappop(pairq)
			wait += t
		else:
			t = pairs[i][0]
	return wait
N = int(input().strip())
pairs = []
for _ in range(N):
	pair = tuple([int(i) for i in input().strip().split()])
	pairs.append(pair)
print(totalwait(pairs) // N)


import heapq
n = int(input())
orders = []
for i in range(n):
	(start, time) = [int(j) for j in input().split()]
	orders.append((time, start))
orders.sort(key=lambda a: a[1])
orders.reverse()
total = 0
pq = [orders[-1]]
i = orders[-1][1]
orders.pop()
added = 0
while pq or orders:
	while orders and orders[-1][1] <= i:
		heapq.heappush(pq, orders[-1])
		orders.pop()
	if pq:
		next_value = heapq.heappop(pq)
		i += next_value[0]
		total += i - next_value[1]
	else:
		i = orders[-1][1]
print(int(total / n))


from operator import itemgetter
import heapq
inTheDoor = []
N = int(input())
csInO = []
for i in range(0, N):
	inp = input().split()
	next = list(map(int, [inp[1], inp[0]]))
	csInO.append(next)
csInO.sort(key=itemgetter(1))
Time = 0
door = 0
waitT = 0
while True:
	while door < N and csInO[door][1] <= Time:
		heapq.heappush(inTheDoor, csInO[door])
		door += 1
	if len(inTheDoor) > 0:
		chosen = heapq.heappop(inTheDoor)
		Time += chosen[0]
		waitT += Time - chosen[1]
	else:
		Time = csInO[door][1]
	if door >= N and len(inTheDoor) == 0:
		break
print(int(waitT / N))


from heapq import heappush, heappop

def get_input():
	no_of_cust = int(input())
	customer_list = []
	for i in range(0, no_of_cust):
		(order_time, prep_time) = input().strip().split(' ')
		customer_order = (int(order_time), int(prep_time))
		customer_list.append(customer_order)
	customer_list.sort()
	c_order_list = []
	for c_order in customer_list:
		c_order_list.append((c_order[1], c_order[0]))
	return c_order_list

def build_customer_priority_heap(customer_list, customer_priority_heap, current_time):
	for customer_order in list(customer_list):
		if get_order_time(customer_order) <= current_time:
			heappush(customer_priority_heap, customer_order)
			customer_list.remove(customer_order)
	return (customer_priority_heap, customer_list)

def get_prep_time(customer_order):
	return customer_order[0]

def get_order_time(customer_order):
	return customer_order[1]

def get_avg_wait_time():
	customer_list = get_input()
	current_time = 0
	customer_priority_heap = []
	(customer_priority_heap, customer_list) = build_customer_priority_heap(customer_list, customer_priority_heap, current_time)
	wait_time_list = []
	while len(customer_priority_heap) != 0 or len(customer_list) != 0:
		if len(customer_priority_heap) != 0:
			node = heappop(customer_priority_heap)
			wait_time = current_time - get_order_time(node) + get_prep_time(node)
			wait_time_list.append(wait_time)
			current_time = current_time + get_prep_time(node)
		else:
			current_time = get_order_time(customer_list[0])
		(customer_priority_heap, customer_list) = build_customer_priority_heap(customer_list, customer_priority_heap, current_time)
	print(int(sum(wait_time_list) / len(wait_time_list)))
get_avg_wait_time()


import heapq
all_customers = []
waiting_customers = []
N = int(input())
for _ in range(N):
	(t, span) = map(int, input().split())
	heapq.heappush(all_customers, (t, span))
res = 0
time = 0
while all_customers or waiting_customers:
	if not waiting_customers:
		(start_time, span) = heapq.heappop(all_customers)
	else:
		(span, start_time) = heapq.heappop(waiting_customers)
	res += span + max(time - start_time, 0)
	time = max(time, start_time) + span
	while all_customers and all_customers[0][0] < time:
		(start_time, span) = heapq.heappop(all_customers)
		heapq.heappush(waiting_customers, (span, start_time))
print(res // N)


import heapq, sys
N = int(sys.stdin.readline())
X = sorted((list(map(int, sys.stdin.readline().split())) for _ in range(N)))
time = 0
total_time = 0
queue = []
while X or queue:
	while X and (not queue or X[0][0] <= time):
		(T, L) = X.pop(0)
		heapq.heappush(queue, (L, T))
		time = max(time, T)
	(L, T) = heapq.heappop(queue)
	time += L
	total_time += time - T
print(total_time // N)


import heapq

def minWait(allOrders):
	totalWaitTime = 0
	numOrders = len(allOrders)
	if numOrders == 0:
		return 0
	pendingOrders = []
	currentTime = allOrders[0][0]
	loop = True
	while loop:
		while len(allOrders) != 0 and allOrders[0][0] <= currentTime:
			order = heapq.heappop(allOrders)
			heapq.heappush(pendingOrders, (order[1], order[0]))
		if len(pendingOrders) != 0:
			minWaitOrder = heapq.heappop(pendingOrders)
			waitTime = currentTime - minWaitOrder[1] + minWaitOrder[0]
			totalWaitTime += waitTime
			currentTime += minWaitOrder[0]
		else:
			currentTime += 1
		if len(pendingOrders) == 0 and len(allOrders) == 0:
			loop = False
	return totalWaitTime / numOrders
n = int(input())
allOrders = []
for i in range(n):
	line = input().split()
	(l, t) = (int(line[0]), int(line[1]))
	heapq.heappush(allOrders, (l, t))
print(int(minWait(allOrders)))


import heapq, sys
N = int(sys.stdin.readline())
X = sorted((list(map(int, sys.stdin.readline().split())) for _ in range(N)))
time = 0
total_time = 0
queue = []
while X or queue:
	while X and (not queue or X[0][0] <= time):
		(T, L) = X.pop(0)
		heapq.heappush(queue, (L, T))
		time = max(time, T)
	(L, T) = heapq.heappop(queue)
	time += L
	total_time += time - T
print(total_time // N)


import heapq
from _heapq import heappush

class Cus:

	def __init__(self, arr, req):
		self.arr = arr
		self.req = req

	def __repr__(self):
		return repr((self.arr, self.req))

	def reverse(self):
		return (self.req, self.arr)

def addCus(cus, h, time, ind, totaltime):
	i = ind
	t = 0
	while i + 1 < len(cus):
		if cus[i + 1].arr <= time:
			i += 1
			t += time - cus[i].arr
			heapq.heappush(h, cus[i].reverse())
		else:
			break
	return (h, i, totaltime + t)
N = int(input())
cus = []
for _ in range(N):
	aux = [int(x) for x in input().split()]
	cus.append(Cus(aux[0], aux[1]))
cus = sorted(cus, key=lambda cus: cus.arr)
h = []
time = cus[0].arr
ind = 0
totaltime = 0
heapq.heappush(h, cus[0].reverse())
(h, ind, totaltime) = addCus(cus, h, time, ind, totaltime)
while len(h) != 0 or ind != N - 1:
	if len(h) != 0:
		(req, arr) = heapq.heappop(h)
		time = time + req
		totaltime += req * (len(h) + 1)
		(h, ind, totaltime) = addCus(cus, h, time, ind, totaltime)
	else:
		ind += 1
		time = cus[ind].arr
		heapq.heappush(h, cus[ind].reverse())
		(h, ind, totaltime) = addCus(cus, h, time, ind, totaltime)
print(int(totaltime / N))


from heapq import heappush, heappop

def generate_problem():
	num_customers = int(input())
	customers = []
	for _ in range(num_customers):
		line = input().strip().split()
		(arrival, order) = (int(line[0]), int(line[1]))
		customers.append((arrival, order))
	return sorted(customers, key=lambda x: x[0])

def min_average_wait(arrivals):
	total_customers = len(arrivals)
	wait_times = 0
	current_time = 0
	order_queue = []
	while arrivals or order_queue:
		while arrivals != [] and arrivals[0][0] <= current_time:
			customer = arrivals.pop(0)
			new_order = (customer[1], customer[0])
			heappush(order_queue, new_order)
		if order_queue != []:
			(cook_time, arrival_time) = heappop(order_queue)
			wait = current_time - arrival_time
			wait_times += wait + cook_time
			current_time += cook_time
		elif arrivals != []:
			current_time = arrivals[0][0]
	return wait_times // total_customers
problem = generate_problem()
print(min_average_wait(problem))


class Heap:

	def __init__(self, ismin=True):
		self.arr = []
		self.m = ismin

	def swap(self, i, j):
		temp = self.arr[i]
		self.arr[i] = self.arr[j]
		self.arr[j] = temp

	def heapifyUp(self, i):
		if i == 0:
			return
		if self.m:
			if self.arr[i][1] < self.arr[i // 2][1]:
				self.swap(i, i // 2)
				self.heapifyUp(i // 2)
		elif self.arr[i][1] > self.arr[i // 2][1]:
			self.swap(i, i // 2)
			self.heapifyUp(i // 2)

	def heapifyDown(self, i):
		if self.m:
			if i * 2 < len(self.arr):
				j = i * 2
				m = self.arr[j][1]
				if j + 1 < len(self.arr) and m > self.arr[j + 1][1]:
					j = j + 1
					m = self.arr[j][1]
				if m < self.arr[i][1]:
					self.swap(i, j)
					self.heapifyDown(j)
		elif i * 2 < len(self.arr):
			j = i * 2
			m = self.arr[j][1]
			if j + 1 < len(self.arr) and m < self.arr[j + 1][1]:
				j = j + 1
				m = self.arr[j][1]
			if m > self.arr[i][1]:
				self.swap(i, j)
				self.heapifyDown(j)

	def add(self, v):
		self.arr.append(v)
		self.heapifyUp(len(self.arr) - 1)

	def root(self):
		return self.arr[0]

	def len(self):
		return len(self.arr)

	def remove(self, v):
		k = len(self.arr) - 1
		i = self.arr.index(v)
		self.swap(i, k)
		del self.arr[k]
		self.heapifyDown(i)
n = int(input().strip())
i = 0
h1 = Heap()
while i < n:
	(t, l) = map(int, input().strip().split())
	h1.add((l, t))
	i += 1
tim = 0
h = Heap()
sum = 0
k = 0
i = 0
while h1.len() > 0:
	(l, t) = h1.root()
	h1.remove(h1.root())
	if tim == 0:
		tim = t + l
		sum = l
	elif t > tim:
		while h.len() > 0 and t > tim:
			(t1, l1) = h.root()
			h.remove(h.root())
			tim = max(tim, t1) + l1
			sum += tim - t1
			k += 1
		h.add((t, l))
	else:
		h.add((t, l))
while h.len() > 0:
	(t, l) = h.root()
	h.remove(h.root())
	tim = max(tim, t) + l
	sum += tim - t
print('%i' % (sum // n))


def min_heapify(A, i):
	l = i * 2 + 1
	r = i * 2 + 2
	n = len(A)
	i_sm = i
	if l < n and A[l] < A[i]:
		i_sm = l
	if r < n and A[r] < A[i_sm]:
		i_sm = r
	if i != i_sm:
		(A[i], A[i_sm]) = (A[i_sm], A[i])
		min_heapify(A, i_sm)

def min_bubble_up(A, i):
	p = (i - 1) // 2
	if p >= 0 and A[i] < A[p]:
		(A[p], A[i]) = (A[i], A[p])
		min_bubble_up(A, p)

def extract_min(A):
	n = len(A)
	i_n = n - 1
	if n < 1:
		raise ValueError('Heap underflow')
	elif n == 1:
		return A.pop(0)
	elif n > 1:
		m = A[0]
		A[0] = A.pop(i_n)
		min_heapify(A, 0)
		return m

def min_insert(A, z):
	A.append(z)
	n = len(A)
	if n > 1:
		i_n = n - 1
		min_bubble_up(A, i_n)

class CustomerByArrival:

	def __init__(self, a, s):
		self.a = a
		self.s = s

	def __lt__(self, other):
		return self.a < other.a

	def __gt__(self, other):
		return self.a > other.a

class CustomerByServingTime:

	def __init__(self, a, s):
		self.a = a
		self.s = s

	def __lt__(self, other):
		return self.s < other.s

	def __gt__(self, other):
		return self.s > other.s
line = []
q = int(input())
for i in range(0, q):
	(a, s) = input().split()
	c = CustomerByArrival(int(a), int(s))
	min_insert(line, c)
w = []
batch = []
t = 0
while True:
	while len(line) > 0 and t >= line[0].a:
		c = extract_min(line)
		min_insert(batch, CustomerByServingTime(c.a, c.s))
	if len(batch) > 0:
		c = extract_min(batch)
		s = t + c.s - c.a
		w.append(s)
		t += c.s
	elif len(line) > 0 and line[0].a > t:
		t = line[0].a
	if len(line) == 0 and len(batch) == 0:
		break
s = int(sum(w) / len(w))
print(s)


class Heap:

	def __init__(self, compare_func=lambda x, y: x < y):
		self.heap = [0]
		self.compare_func = compare_func

	def __len__(self):
		return len(self.heap) - 1

	def push(self, value):
		self.heap.append(value)
		self._upward_heapify()

	def pop(self):
		if len(self.heap) == 1:
			return self.heap.pop()
		else:
			value = self.heap[1]
			self.heap[1] = self.heap[-1]
			self.heap.pop()
			self._downward_heapify()
			return value

	def peak(self):
		return self.heap[1]

	def is_empty(self):
		if len(self.heap) == 1:
			return True
		else:
			return False

	def _upward_heapify(self):
		index = len(self.heap) - 1
		while index > 1 and self.compare_func(self.heap[index], self.heap[index // 2]):
			(self.heap[index], self.heap[index // 2]) = (self.heap[index // 2], self.heap[index])
			index //= 2

	def _downward_heapify(self):
		index = 1
		while True:
			if index * 2 + 1 < len(self.heap):
				smaller_child_index = index * 2 + 1 if self.compare_func(self.heap[2 * index + 1], self.heap[2 * index]) else index * 2
			elif index * 2 < len(self.heap):
				smaller_child_index = index * 2
			else:
				return
			if self.compare_func(self.heap[smaller_child_index], self.heap[index]):
				(self.heap[smaller_child_index], self.heap[index]) = (self.heap[index], self.heap[smaller_child_index])
				index = smaller_child_index
			else:
				return

class Customer:

	def __init__(self, come_time, wait_time):
		self.come_time = come_time
		self.wait_time = wait_time

def main():
	n = int(input())
	out_queue_customers = Heap(lambda x, y: x.come_time < y.come_time)
	for i in range(n):
		(t, l) = input().split()
		out_queue_customers.push(Customer(int(t), int(l)))
	total_wait_time = 0
	current_time = 0
	in_queue_customers = Heap(lambda x, y: x.wait_time < y.wait_time)
	while not (out_queue_customers.is_empty() and in_queue_customers.is_empty()):
		while not out_queue_customers.is_empty():
			if out_queue_customers.peak().come_time <= current_time:
				customer = out_queue_customers.pop()
				in_queue_customers.push(customer)
				total_wait_time += current_time - customer.come_time
			else:
				break
		if in_queue_customers.is_empty():
			in_queue_customers.push(out_queue_customers.pop())
			current_time = in_queue_customers.peak().come_time
			while not out_queue_customers.is_empty():
				if out_queue_customers.peak().come_time == current_time:
					in_queue_customers.push(out_queue_customers.pop())
				else:
					break
		cook_time = in_queue_customers.pop().wait_time
		current_time += cook_time
		total_wait_time += cook_time * (len(in_queue_customers) + 1)
	print(total_wait_time // n)
main()


import heapq
n = int(input())
orders = []
instore = []
for _ in range(n):
	(a, b) = (int(x) for x in input().strip().split(' '))
	heapq.heappush(orders, (a, b))
wait_time = 0
time = 0
while orders or instore:
	while orders and orders[0][0] <= time:
		(a, b) = heapq.heappop(orders)
		heapq.heappush(instore, (b, a))
	if instore:
		(cook_time, arrival) = heapq.heappop(instore)
		time = max(time, arrival)
		time = time + cook_time
		wait_time += time - arrival
	else:
		time = orders[0][0]
print(int(wait_time / n))


from heapq import heappush, heappop, heapify
N = int(input())
customers = []
waitlist = []
for _ in range(N):
	inputs = input().split()
	customers.append((int(inputs[0]), int(inputs[1])))
heapify(customers)
current_time = 0
total_wait = 0
while len(customers) > 0 or len(waitlist) > 0:
	order_time = 0
	cook_time = 0
	if len(waitlist) == 0:
		(order_time, cook_time) = heappop(customers)
		if current_time < order_time:
			current_time = order_time
	else:
		(cook_time, order_time) = heappop(waitlist)
		if current_time > order_time:
			total_wait += current_time - order_time
	total_wait += cook_time
	current_time += cook_time
	while len(customers) > 0 and customers[0][0] <= current_time:
		(order_time, cook_time) = heappop(customers)
		heappush(waitlist, (cook_time, order_time))
print(int(total_wait / N))


import heapq
pizzaq = []
times_in = []
customers = set()
wait_times = []
N = int(input())
last_time = 1
for i in range(N):
	(t, l) = [int(x) for x in input().split()]
	customers.add(i)
	heapq.heappush(times_in, (t, l, i))
	if t > last_time:
		last_time = t
oven_time = 0
current_order = None
t = times_in[0][0]
while customers:
	while times_in and times_in[0][0] == t:
		(ti, l, i) = heapq.heappop(times_in)
		heapq.heappush(pizzaq, (l, ti, i))
	if not oven_time:
		if current_order:
			wait_times.append(t - current_order[1])
			customers.remove(current_order[2])
		if pizzaq:
			current_order = heapq.heappop(pizzaq)
			oven_time = current_order[0]
		else:
			current_order = None
	if not oven_time:
		if times_in:
			elapsed_time = times_in[0][0] - t
		else:
			continue
	elif times_in:
		elapsed_time = min(oven_time, times_in[0][0] - t)
	else:
		elapsed_time = oven_time
	if oven_time:
		oven_time -= elapsed_time
	t += elapsed_time
print(int(sum(wait_times) / len(wait_times)))


from heapq import *
n = int(input())
orders = sorted(([int(x) for x in input().split()] for _ in range(n)))
waiting = []
time = 0
total_waiting_time = 0
for (order_time, cooking_time) in orders:
	while waiting and time < order_time:
		(waiting_cooking_time, waiting_order_time) = heappop(waiting)
		time += waiting_cooking_time
		total_waiting_time += time - waiting_order_time
	time = max(time, order_time)
	heappush(waiting, (cooking_time, order_time))
while waiting:
	(waiting_cooking_time, waiting_order_time) = heappop(waiting)
	time += waiting_cooking_time
	total_waiting_time += time - waiting_order_time
print(total_waiting_time // n)


from heapq import heappush, heappop
N = int(input())
C = []
for __ in range(N):
	i = input().split()
	C.append([int(i[1]), int(i[0])])
time = 0
wait_time = time
orders = []
while C != [] or orders != []:
	for i in filter(lambda x: x[1] <= time, C):
		heappush(orders, i)
	if orders == []:
		time = min(map(lambda x: x[1], C))
	else:
		C = list(filter(lambda x: x[1] > time, C))
		order = heappop(orders)
		time += order[0]
		wait_time += time - order[1]
print(int(wait_time / N))


import bisect
import heapq
from collections import deque
n = int(input())
orders = []
for _ in range(n):
	info = input().split(' ')
	bisect.insort(orders, (int(info[0]), int(info[1])))
wait = 0
t = 0
k = n
available = []
i = 0
while available or i < n:
	while i < n and orders[i][0] <= t:
		heapq.heappush(available, (orders[i][1], orders[i][0]))
		i += 1
	if not available:
		t = orders[i][0]
		continue
	(p, arrival) = heapq.heappop(available)
	t += p
	wait += t - arrival
print(wait // n)


import heapq, sys
N = int(sys.stdin.readline())
X = sorted((list(map(int, sys.stdin.readline().split())) for _ in range(N)))
time = 0
total_time = 0
queue = []
while X or queue:
	while X and (not queue or X[0][0] <= time):
		(T, L) = X.pop(0)
		heapq.heappush(queue, (L, T))
		time = max(time, T)
	(L, T) = heapq.heappop(queue)
	time += L
	total_time += time - T
print(total_time // N)


from heapq import heappush, heappop
ready = []
waiting = []
N = int(input())
maxTime = 0
for i in range(N):
	(t, l) = [int(j) for j in input().strip().split(' ')]
	heappush(waiting, (t, l))
	maxTime = max(maxTime, t + l)
minute = 0
timeCooked = 0
pizzasComplete = 0
while len(ready) > 0 or len(waiting) > 0:
	while True:
		if len(waiting) == 0:
			break
		if waiting[0][0] <= minute:
			(t, l) = heappop(waiting)
			heappush(ready, (l, t))
		else:
			break
	if len(ready) > 0:
		(l, t) = heappop(ready)
		minute += l
		timeCooked += abs(t - minute)
		pizzasComplete += 1
	else:
		(t, l) = waiting[0]
		minute = t
print(int(timeCooked / pizzasComplete))


import heapq

class Customer(object):

	def __init__(self, arrival_time, cook_time):
		self.arrival_time = arrival_time
		self.cook_time = cook_time
custs = []
waitlist = []
n = int(input())
for _ in range(n):
	(t, l) = map(int, input().split())
	cust = Customer(t, l)
	heapq.heappush(custs, (t, l))
tot_time = 0
end_time = 0
while len(custs) != 0 or len(waitlist) != 0:
	if waitlist:
		cur = heapq.heappop(waitlist)
		end_time = max(end_time, cur[1]) + cur[0]
		tot_time += end_time - cur[1]
	else:
		cur = heapq.heappop(custs)
		end_time = max(end_time, cur[0]) + cur[1]
		tot_time += end_time - cur[0]
	while len(custs) != 0 and custs[0][0] <= end_time:
		to_append = heapq.heappop(custs)
		heapq.heappush(waitlist, (to_append[1], to_append[0]))
print(tot_time // n)


from heapq import *
import sys

class NoCustomersException(Exception):
	pass

class Restaurant:

	def __init__(self, future_customers):
		heapify(future_customers)
		self.future_customers = future_customers
		self.current_customers = []
		self.time = 0
		self.total_wait_time = 0
		self.num_customers = len(future_customers)

	def advance(self):
		if len(self.current_customers) > 0:
			(li, ti) = heappop(self.current_customers)
		elif len(self.future_customers) > 0:
			(ti, li) = heappop(self.future_customers)
			self.time = ti
		else:
			raise NoCustomersException
		self.time += li
		self.total_wait_time += self.time - ti
		while len(self.future_customers) > 0 and self.future_customers[0][0] <= self.time:
			cust = heappop(self.future_customers)
			heappush(self.current_customers, (cust[1], cust[0]))
n = int(sys.stdin.readline())
future_customers = []
for i in range(n):
	[ti, li] = sys.stdin.readline().split()
	future_customers.append((int(ti), int(li)))
rest = Restaurant(future_customers)
while True:
	try:
		rest.advance()
	except NoCustomersException:
		print(rest.total_wait_time // rest.num_customers)
		break


from heapq import heappush, heappop
arrival_queue = []
cooking_queue = []
waiting_time = 0
i = int(input())
for _ in range(i):
	(arrival, cooking_time) = [int(x) for x in input().split(' ')]
	heappush(arrival_queue, (arrival, cooking_time))
while arrival_queue or cooking_queue:
	if not cooking_queue:
		(arrival, cooking_time) = heappop(arrival_queue)
		cooking_queue = [(cooking_time, arrival)]
		time = arrival
	(cooking_time, arrival) = heappop(cooking_queue)
	time += cooking_time
	waiting_time += time - arrival
	while arrival_queue and arrival_queue[0][0] <= time:
		(arrival, cooking_time) = heappop(arrival_queue)
		heappush(cooking_queue, (cooking_time, arrival))
print(waiting_time // i)


import heapq
n = int(input())
q = []
for i in range(n):
	q.append([int(x) for x in input().split()])
q.sort(key=lambda x: x[0] * 10 ** 9 + x[1])
loss = 0
t0 = 0
heap = []
head = 0
while head < n or len(heap) > 0:
	if len(heap) == 0:
		t0 = q[head][0] + q[head][1]
		loss += q[head][1]
		head += 1
	else:
		dt0 = heapq.heappop(heap)
		t0 += dt0
		loss += dt0 * (len(heap) + 1)
	while head < n and q[head][0] <= t0:
		heapq.heappush(heap, q[head][1])
		loss += t0 - q[head][0]
		head += 1
print(loss // n)


import heapq
import sys

class pizzaOrder:

	def __init__(self, time, duration):
		self.time = time
		self.duration = duration

	def __lt__(self, other):
		return self.time < other.time

class pizzaOrderToServe:

	def __init__(self, time, duration):
		self.time = time
		self.duration = duration

	def __lt__(self, other):
		return self.duration < other.duration
numberClients = int(sys.stdin.readline())
listOfOrders = []
currentTime = -1
waitTime = 0
oldCurrentTime = -1
readyToBeServed = []
clientsServed = 0
for line in sys.stdin:
	(time, duration) = [int(x) for x in line.split(' ')]
	newOrder = pizzaOrder(time, duration)
	heapq.heappush(listOfOrders, newOrder)
currentTime = listOfOrders[0].time
while True:
	if clientsServed < numberClients and listOfOrders[0].time <= currentTime:
		clientsServed += 1
		order = heapq.heappop(listOfOrders)
		orderToServe = pizzaOrderToServe(order.time, order.duration)
		heapq.heappush(readyToBeServed, orderToServe)
	elif not readyToBeServed:
		if clientsServed < numberClients:
			currentTime = listOfOrders[0].time
		else:
			break
	else:
		orderToServe = heapq.heappop(readyToBeServed)
		currentTime += orderToServe.duration
		waitTime += currentTime - orderToServe.time
print(int(waitTime / numberClients))


import math

def main():
	customers = []
	heap = MinHeap()
	clock = 0
	cook_time_left = 0
	order_placed = 0
	total_wait_time = 0
	N = int(input().strip())
	for _ in range(N):
		customer = tuple([int(v) for v in input().strip().split()])
		customers.append(customer)
	customers = sorted(customers)
	for (current_time, cook_time) in customers:
		while clock < current_time:
			if cook_time_left == 0 and heap:
				(cook_time_left, order_placed) = heap.extract_min()
			if cook_time_left > 0:
				if current_time - clock >= cook_time_left:
					clock += cook_time_left
					cook_time_left = 0
					total_wait_time += clock - order_placed
				else:
					cook_time_left -= current_time - clock
					clock = current_time
			else:
				clock = current_time
		heap.add((cook_time, current_time))
	if cook_time_left == 0 and heap:
		(cook_time_left, order_placed) = heap.extract_min()
	while cook_time_left > 0:
		clock += cook_time_left
		cook_time_left = 0
		total_wait_time += clock - order_placed
		if heap:
			(cook_time_left, order_placed) = heap.extract_min()
	print(total_wait_time // N)

class MinHeap(object):

	def __init__(self):
		self.heap = []

	def __bool__(self):
		return bool(self.heap)

	def add(self, val):
		self.heap.append(val)
		self.__sift_up(len(self.heap) - 1)

	def extract_min(self):
		minimum = self.heap.pop(0) if self.heap else None
		if self.heap:
			self.heap.insert(0, self.heap.pop())
			self.__sift_down(0)
		return minimum

	def __sift_down(self, root):
		left = root * 2 + 1 if root * 2 + 1 < len(self.heap) else None
		right = root * 2 + 2 if root * 2 + 2 < len(self.heap) else None
		proposed = left if left and self.heap[root] > self.heap[left] else root
		proposed = right if right and self.heap[proposed] > self.heap[right] else proposed
		if proposed != root:
			self.__swap(proposed, root)
			self.__sift_down(proposed)

	def __sift_up(self, child):
		parent = math.ceil(child / 2) - 1
		if parent >= 0 and self.heap[child] < self.heap[parent]:
			self.__swap(child, parent)
			self.__sift_up(parent)

	def __swap(self, i, j):
		temp = self.heap[i]
		self.heap[i] = self.heap[j]
		self.heap[j] = temp
main()


import heapq
prio_queue = []
time = 0
time_list = []
total_time = 0
N = int(input())
for num in range(1, N + 1):
	(a, b) = input().strip().split()
	time_list.append([int(a), int(b)])
time_list = sorted(time_list)
while time_list or prio_queue:
	while len(time_list) != 0 and (len(prio_queue) == 0 or time_list[0][0] <= time):
		(arrival_time, cook_time) = time_list.pop(0)
		heapq.heappush(prio_queue, (cook_time, arrival_time))
		time = max(time, arrival_time)
	(cook_time, arrival_time) = heapq.heappop(prio_queue)
	time += cook_time
	total_time += time - arrival_time
print(int(total_time / N))


from heapq import *
orders = []
queue = []
wait_times = []
time_elapsed = 0
n = int(input().strip())
for i in range(n):
	(time_entered, time_to_complete) = map(int, input().strip().split(' '))
	heappush(orders, (time_entered, time_to_complete))
while orders or queue:
	while orders and orders[0][0] <= time_elapsed:
		(entered, duration) = heappop(orders)
		heappush(queue, (duration, entered))
	if not queue:
		(entered, duration) = heappop(orders)
		time_elapsed = entered
		heappush(queue, (duration, entered))
	(cook_duration, cook_entered_time) = heappop(queue)
	wait_time = time_elapsed - cook_entered_time
	time_elapsed += cook_duration
	wait_time += cook_duration
	wait_times.append(wait_time)
print(int(sum(wait_times) / n))


import heapq
N = int(input().strip())
data = []
for _ in range(N):
	data.append(list(map(int, input().strip().split())))
data = sorted(data, key=lambda x: x[0])
orders = []
t_completed = 0
wait_time = 0
for (t, l) in data:
	wait_time -= t
	while t > t_completed and len(orders) > 0:
		order = heapq.heappop(orders)
		t_completed += order
		wait_time += t_completed
	if t > t_completed:
		t_completed = t
	heapq.heappush(orders, l)
while len(orders) > 0:
	order = heapq.heappop(orders)
	t_completed += order
	wait_time += t_completed
print(wait_time // N)


from heapq import *
n = int(input())
o = [tuple(map(int, input().split())) for _ in range(n)]
o.sort(reverse=True)
x = 0
w = 0
h = []
while o or h:
	if h:
		(a, b) = heappop(h)
		x += a
		w += x - b
	else:
		x = o[-1][0]
	while o and o[-1][0] <= x:
		heappush(h, o.pop()[::-1])
print(w // n)


from collections import namedtuple
from heapq import heappush, heappop

def mean(xs):
	return sum(xs) // len(xs)

class Scheduler(object):
	Job = namedtuple('Job', ['duration', 'submitted'])

	def __init__(self):
		(self.queue, self.now) = ([], 0)
		self.waittimes = []

	def _schedule(self, job):
		self.now = max(job.submitted, self.now) + job.duration
		self.waittimes.append(self.now - job.submitted)

	def submit(self, job):
		self.run(job.submitted)
		heappush(self.queue, job)

	def run(self, barrier=None):
		while self.queue and (barrier is None or self.now < barrier):
			self._schedule(heappop(self.queue))

	def waittime(self):
		return mean(self.waittimes)
orders = [tuple(map(int, input().split())) for N in range(int(input()))]
scheduler = Scheduler()
for (T, L) in sorted(orders):
	scheduler.submit(Scheduler.Job(submitted=T, duration=L))
scheduler.run()
print(int(scheduler.waittime()))


class PizzaHeap:

	def __init__(self):
		self.h = []

	def peek(self):
		if len(self.h) == 0:
			return None
		return self.h[0]

	def pop_min(self):
		(self.h[0], self.h[-1]) = (self.h[-1], self.h[0])
		min_el = self.h.pop()
		i = 0
		if i < len(self.h):
			while self.violation_at(i):
				left_el = self.h[2 * i + 1] if 2 * i + 1 < len(self.h) else (-1, 9999999999)
				right_el = self.h[2 * i + 2] if 2 * i + 2 < len(self.h) else (-1, 9999999999)
				if left_el[1] < right_el[1]:
					(self.h[i], self.h[2 * i + 1]) = (self.h[2 * i + 1], self.h[i])
					i = 2 * i + 1
				else:
					(self.h[i], self.h[2 * i + 2]) = (self.h[2 * i + 2], self.h[i])
					i = 2 * i + 2
		return min_el

	def add(self, data):
		self.h.append(data)
		i = len(self.h) - 1
		j = int((i - 1) / 2)
		while j >= 0 and self.violation_at(j):
			(self.h[i], self.h[j]) = (self.h[j], self.h[i])
			i = j
			j = int((i - 1) / 2)

	def violation_at(self, i):
		right_ok = 2 * i + 2 >= len(self.h) or self.h[2 * i + 2][1] > self.h[i][1]
		left_ok = 2 * i + 1 >= len(self.h) or self.h[2 * i + 1][1] > self.h[i][1]
		return not right_ok or not left_ok
N = int(input())
customers = []
pizza_heap = PizzaHeap()
for _ in range(N):
	(T, L) = list(map(int, input().strip().split(' ')))
	customers.append((T, L))
customers = sorted(customers, key=lambda x: x[0], reverse=True)
customer_count = len(customers)
total_wait_time = 0
while pizza_heap.peek() != None or len(customers) > 0:
	if pizza_heap.peek() != None:
		customer = pizza_heap.pop_min()
		current_time += customer[1]
		curr_wait_time = current_time - customer[0]
		total_wait_time += curr_wait_time
	else:
		customer = customers.pop()
		current_time = customer[0]
		pizza_heap.add(customer)
		continue
	while len(customers) > 0 and customers[-1][0] < current_time:
		pizza_heap.add(customers.pop())
print(int(total_wait_time / customer_count))


import heapq
heap1 = []
heap2 = []
N = int(input())
for _ in range(N):
	(T, L) = [int(i) for i in input().split(' ')]
	heapq.heappush(heap1, (T, L))
t = w = 0
for _ in range(N):
	if not heap2 and heap1[0][0] > t:
		t = heap1[0][0]
	while heap1 and heap1[0][0] <= t:
		el = heapq.heappop(heap1)
		heapq.heappush(heap2, (el[1], el[0]))
	el = heapq.heappop(heap2)
	t += el[0]
	w += t - el[1]
print(w // N)


import sys, heapq
n = int(input())
customer_requests = sorted((list(map(int, input().split())) for _ in range(n)))
time = 0
total_time = 0
queue = []
while customer_requests or queue:
	while customer_requests and (not queue or customer_requests[0][0] <= time):
		(t, l) = customer_requests.pop(0)
		heapq.heappush(queue, (l, t))
		time = max(time, t)
	(l, t) = heapq.heappop(queue)
	time += l
	total_time += time - t
print(total_time // n)


import heapq as q
line_ct = int(input())
input_heap = []
job_queue = []
now = 0
total_wait = 0
for _ in range(line_ct):
	(time, dur) = map(int, input().split())
	q.heappush(input_heap, (time, dur))
while input_heap:
	time = input_heap[0][0]
	while time > now:
		if job_queue:
			(job_time, ord_time) = q.heappop(job_queue)
			now += job_time
			total_wait += now - ord_time
		else:
			now = time
	while input_heap and input_heap[0][0] <= now:
		(time, dur) = q.heappop(input_heap)
		q.heappush(job_queue, (dur, time))
while job_queue:
	(job_time, ord_time) = q.heappop(job_queue)
	now += job_time
	total_wait += now - ord_time
print(total_wait // line_ct)


from heapq import heappush, heappop
n = int(input())
(wait, cur) = (0, 0)
heap = []
for _ in range(n):
	(time, pizza) = map(int, input().strip().split())
	heappush(heap, (pizza, time))
while len(heap) != 0:
	temp = []
	while len(heap) != 0 and heap[0][1] > cur:
		(pizza, time) = heappop(heap)
		heappush(temp, (time, pizza))
	if len(heap) != 0:
		(pizza, time) = heappop(heap)
		cur += pizza
		wait += cur - time
	else:
		(time, pizza) = heappop(temp)
		cur = time + pizza
		wait += pizza
	while len(temp) != 0:
		(time, pizza) = heappop(temp)
		heappush(heap, (pizza, time))
print(wait // n)


from heapq import *
orders = []
queue = []
wait_times = []
time_elapsed = 0
n = int(input())
for i in range(n):
	(time_entered, time_to_complete) = (int(i) for i in input().split())
	heappush(orders, (time_entered, time_to_complete))
while orders or queue:
	while orders and orders[0][0] <= time_elapsed:
		(entered, duration) = heappop(orders)
		heappush(queue, (duration, entered))
	if not queue:
		(entered, duration) = heappop(orders)
		time_elapsed = entered
		heappush(queue, (duration, entered))
	(cook_duration, cook_entered_time) = heappop(queue)
	wait_time = time_elapsed - cook_entered_time
	time_elapsed += cook_duration
	wait_time += cook_duration
	wait_times.append(wait_time)
print(int(sum(wait_times) / n))


import heapq

class PriorityQueue:

	def __init__(self):
		self._queue = []
		self._index = 0

	def put(self, item, priority):
		heapq.heappush(self._queue, (priority, self._index, item))
		self._index += 1

	def get(self):
		return heapq.heappop(self._queue)[-1]

	def empty(self):
		return len(self._queue) <= 0
n = int(input())
a = PriorityQueue()
b = PriorityQueue()
for _ in range(n):
	i = list(map(int, input().split()))
	a.put(i, i[0])
firstCust = a.get()
waitTime = firstCust[1]
firstCust = firstCust[0]
totalTime = waitTime
while not a.empty():
	item = a.get()
	actualTime = item[0] - firstCust
	if actualTime <= waitTime:
		b.put(item, item[1])
	else:
		if not b.empty():
			a.put(item, item[0])
			item = b.get()
			actualTime = item[0] - firstCust
			totalTime += item[1] + (waitTime - actualTime)
		else:
			totalTime += item[1]
		waitTime += item[1]
while not b.empty():
	item = b.get()
	actualTime = item[0] - firstCust
	totalTime += item[1] + (waitTime - actualTime)
	waitTime += item[1]
print(totalTime // n)


from heapq import *
orders = []
queue = []
wait_times = []
time_elapsed = 0
n = int(input().strip())
for i in range(n):
	(time_entered, time_to_complete) = map(int, input().strip().split(' '))
	heappush(orders, (time_entered, time_to_complete))
while orders or queue:
	while orders and orders[0][0] <= time_elapsed:
		(entered, duration) = heappop(orders)
		heappush(queue, (duration, entered))
	if not queue:
		(entered, duration) = heappop(orders)
		time_elapsed = entered
		heappush(queue, (duration, entered))
	(cook_duration, cook_entered_time) = heappop(queue)
	wait_time = time_elapsed - cook_entered_time
	time_elapsed += cook_duration
	wait_time += cook_duration
	wait_times.append(wait_time)
print(int(sum(wait_times) / n))


from heapq import heappop, heappush, heappushpop
customers = []
n = int(input())
for _ in range(n):
	(t, w) = input().split()
	customers.append((int(t), int(w)))
customers.sort()
totaltime = 0
lastt = 0
queue = []

def f(r):
	tt = 0
	fi = 0
	for (t, w) in r:
		if fi <= t:
			tt += w
			fi = t + w
		else:
			tt += w
			tt += fi - t
			fi = fi + w
	return tt
while customers or queue:
	if queue:
		(_, t, w) = heappop(queue)
		dt = 0
		if lastt <= t:
			dt = w
			lastt = t + w
		else:
			dt = w + (lastt - t)
			lastt += w
		totaltime += dt
	while customers:
		(t, w) = customers[0]
		if t <= lastt or not queue:
			customers.pop(0)
			heappush(queue, (w, t, w))
		else:
			break
print(totaltime // n)


from queue import Queue
from heapq import heappush, heappop
from operator import attrgetter

class Order:

	def __init__(self, placed_time, order_time):
		self.placed_time = placed_time
		self.order_time = order_time

	def __eq__(self, other):
		return self.order_time == other.order_time if isinstance(other, Order) else NotImplemented

	def __gt__(self, other):
		return self.order_time > other.order_time if isinstance(other, Order) else NotImplemented

	def __repr__(self):
		return '(Placed time {}, order_time {})'.format(self.placed_time, self.order_time)
N = int(input())
heap = []
orders = []
order_idx = 0
total_time = 0
elapsed_time = 0
curr_order = None
for n in range(N):
	order = tuple(map(int, input().split(' ')))
	orders.append(Order(*order))
orders.sort(key=attrgetter('placed_time'))
while order_idx != len(orders) or heap:
	if order_idx < len(orders):
		order = orders[order_idx]
	if order_idx < len(orders) and order.placed_time <= elapsed_time or not heap:
		heappush(heap, order)
		order_idx += 1
	else:
		curr_order = heappop(heap)
		if curr_order.placed_time > elapsed_time:
			elapsed_time = curr_order.placed_time
		elapsed_time += curr_order.order_time
		total_time += elapsed_time - curr_order.placed_time
print(total_time // N)


import heapq
numCustomers = int(input())
customers = []
for i in range(numCustomers):
	(tEnter, tCook) = [int(x) for x in input().split()]
	heapq.heappush(customers, (tEnter, tCook))
t = 0
w = 0
orders = []
while customers:
	while len(customers) > 0 and customers[0][0] <= t:
		(tEnter, tCook) = heapq.heappop(customers)
		heapq.heappush(orders, (tCook, tEnter))
	if orders:
		(tCook, tEnter) = heapq.heappop(orders)
		w += t - tEnter + tCook
		t += tCook
	else:
		t = customers[0][0]
while orders:
	(tCook, tEnter) = heapq.heappop(orders)
	w += t - tEnter + tCook
	t += tCook
avgWait = w / numCustomers
print('%d' % int(avgWait))


from heapq import *
N = int(input())
orders = [tuple(map(int, input().split())) for _ in range(N)]
heapify(orders)
(taken, time, total) = ([orders[0][1]], orders[0][0], 0)
heappop(orders)
while taken:
	top = heappop(taken)
	(time, total) = (top + time, total + top * (len(taken) + 1))
	while orders and orders[0][0] <= time:
		(arrival, l) = heappop(orders)
		total += time - arrival
		heappush(taken, l)
	if not taken and orders:
		newtop = heappop(orders)
		heappush(taken, newtop[1])
		time = newtop[0]
print(int(total / N))


from heapq import heappush, heappop, heapify
orders = []
n = int(input().strip())
for _ in range(n):
	orders.append([int(c) for c in input().strip().split(' ')])
orders.sort()
wtotal = 0
pending = []
ctime = 0
tl = 0
while orders or pending:
	while orders:
		(t, l) = orders.pop(0)
		if t <= ctime:
			et = ctime + l
		elif not pending:
			ctime = t
			et = ctime + l
		else:
			orders.insert(0, (t, l))
			break
		heappush(pending, (et, t, l))
	(et, st, ll) = heappop(pending)
	w = et - st
	if not orders:
		w += tl
	wtotal += w
	ctime = et
	if orders:
		pending = [(et + ll, t, l) for (et, t, l) in pending]
	else:
		tl += ll
print(wtotal // n)


import heapq
n = int(input())
times = []
for _ in range(n):
	(tstart, length) = map(int, input().strip().split())
	times.append((tstart, length))
times.sort()
q = []
tnext = 0
tot = 0
for (tstart, length) in times:
	while q and tnext < tstart:
		(l, ts) = heapq.heappop(q)
		tnext += l
		tot += tnext - ts
	heapq.heappush(q, (length, tstart))
	if len(q) == 1:
		tnext = max(tstart, tnext)
while q:
	(l, ts) = heapq.heappop(q)
	tnext += l
	tot += tnext - ts
print(tot // n)


import heapq

def average_wait_time(wait_arrive):
	n = len(wait_arrive)
	heap = []
	total_wait_time = 0
	t = wait_arrive[0][1]
	i = 0
	while wait_arrive[i][1] == t:
		heapq.heappush(heap, wait_arrive[i])
		i += 1
	while i < n or heap:
		if heap:
			cust = heapq.heappop(heap)
			t += cust[0]
			total_wait_time += t - cust[1]
		else:
			t = wait_arrive[i][1]
		while i < n and wait_arrive[i][1] <= t:
			heapq.heappush(heap, wait_arrive[i])
			i += 1
	return total_wait_time // n
n = int(input().strip())
wait_arrive = []
for i in range(n):
	temp = [int(x) for x in input().strip().split()]
	tup = (temp[1], temp[0])
	wait_arrive.append(tup)
wait_arrive.sort(key=lambda tup: tup[1])
print(average_wait_time(wait_arrive))


from heapq import *
orders = []
queue = []
wait_times = []
time_elapsed = 0
n = int(input().strip())
for i in range(n):
	(time_entered, time_to_complete) = map(int, input().strip().split(' '))
	heappush(orders, (time_entered, time_to_complete))
while orders or queue:
	while orders and orders[0][0] <= time_elapsed:
		(entered, duration) = heappop(orders)
		heappush(queue, (duration, entered))
	if not queue:
		(entered, duration) = heappop(orders)
		time_elapsed = entered
		heappush(queue, (duration, entered))
	(cook_duration, cook_entered_time) = heappop(queue)
	wait_time = time_elapsed - cook_entered_time
	time_elapsed += cook_duration
	wait_time += cook_duration
	wait_times.append(wait_time)
print(int(sum(wait_times) / n))


import sys
from operator import itemgetter
n = int(input())
cust = []
start = 1
minv = 0
for i in range(n):
	line = sys.stdin.readline()
	line = line.split()
	cust.append((int(line[0]), int(line[1])))
cust = sorted(cust, key=itemgetter(0))
waiting = [(cust[0][0], cust[0][1])]
del cust[0]
total = 0
prevWait = 0
while len(cust) > 0 or len(waiting) > 0:
	if total == 0:
		total = waiting[0][1]
	else:
		total += prevWait + waiting[0][1] - waiting[0][0]
	if prevWait == 0:
		prevWait = waiting[0][0] + waiting[0][1]
	else:
		prevWait += waiting[0][1]
	del waiting[0]
	if len(cust) > 0:
		for i in range(len(cust)):
			if i == len(cust) - 1:
				waiting.append((cust[i][0], cust[i][1]))
				cust = []
				break
			elif cust[i][0] <= prevWait:
				waiting.append((cust[i][0], cust[i][1]))
			else:
				cust = cust[i:]
				break
		if len(waiting) == 0:
			waiting.append((cust[0][0], cust[0][1]))
			prevWait = cust[0][0]
			del cust[0]
		waiting = sorted(waiting, key=itemgetter(1))
print(int(total / n))


from queue import PriorityQueue

def solve():
	global next_arrival
	queue_arrival = PriorityQueue()
	queue_cook_time = PriorityQueue()
	end_time = 0
	sum_time = 0
	num = int(input())
	for i in range(num):
		(arrival, cook_time) = [int(x) for x in input().split()]
		queue_arrival.put((arrival, cook_time))
	while True:
		next_arrival = 0
		if not queue_arrival.empty():
			next_arrival = queue_arrival.queue[0][0]
			while not queue_arrival.empty() and end_time >= queue_arrival.queue[0][0]:
				(arrival, cook_time) = queue_arrival.get()
				queue_cook_time.put((cook_time, arrival))
		if queue_cook_time.empty():
			if queue_arrival.empty():
				break
			end_time = next_arrival
			continue
		else:
			(cook_time, arrival) = queue_cook_time.get()
		end_time += cook_time
		sum_time += end_time - arrival
	average_time = sum_time // num
	print(average_time)
solve()


import heapq
a = input()
b = []
answers = []
time = 0
time_taken = 0
for i in range(int(a)):
	c = [int(x) for x in input().split()]
	b.append(c)
b.sort()
while b or answers:
	while b and (not answers or b[0][0] <= time):
		(d, e) = b.pop(0)
		heapq.heappush(answers, (e, d))
		time = max(time, d)
	(e, d) = heapq.heappop(answers)
	time += e
	time_taken += time - d
print(time_taken // int(a))


import heapq
time = 0
totalT = 0
queue = []
customers = int(input())
orders = sorted((list(map(int, input().split())) for i in range(customers)))
while orders or queue:
	while orders and (not queue or int(orders[0][0]) <= time):
		(customer, length) = orders.pop(0)
		heapq.heappush(queue, (length, customer))
		time = max(time, int(customer))
	(length, customer) = heapq.heappop(queue)
	time += int(length)
	totalT += time - int(customer)
print(totalT // customers)


from heapq import *
orders = []
queue = []
wait_times = []
time_elapsed = 0
n = int(input().strip())
for i in range(n):
	(time_entered, time_to_complete) = map(int, input().strip().split(' '))
	heappush(orders, (time_entered, time_to_complete))
while orders or queue:
	while orders and orders[0][0] <= time_elapsed:
		(entered, duration) = heappop(orders)
		heappush(queue, (duration, entered))
	if not queue:
		(entered, duration) = heappop(orders)
		time_elapsed = entered
		heappush(queue, (duration, entered))
	(cook_duration, cook_entered_time) = heappop(queue)
	wait_time = time_elapsed - cook_entered_time
	time_elapsed += cook_duration
	wait_time += cook_duration
	wait_times.append(wait_time)
print(int(sum(wait_times) / n))


import heapq
Tasks = []
N = int(input())
for n in range(N):
	Tasks.append([int(x) for x in input().strip().split()])
Tasks.sort()
TotalWaiting = 0
currentTime = 0
currentWaiting = []
i = 0
while i < len(Tasks):
	if not currentWaiting and Tasks[i][0] > currentTime:
		currentTime = Tasks[i][0]
	while i < len(Tasks) and Tasks[i][0] <= currentTime:
		heapq.heappush(currentWaiting, tuple([Tasks[i][1], Tasks[i][0]]))
		i += 1
	task = heapq.heappop(currentWaiting)
	currentTime += task[0]
	TotalWaiting += currentTime - task[1]
	if i >= len(Tasks):
		while currentWaiting:
			task = heapq.heappop(currentWaiting)
			currentTime += task[0]
			TotalWaiting += currentTime - task[1]
print(TotalWaiting // N)


from heapq import *
orders = []
queue = []
wait_times = []
time_elapsed = 0
n = int(input().strip())
for i in range(n):
	(time_entered, time_to_complete) = map(int, input().strip().split(' '))
	heappush(orders, (time_entered, time_to_complete))
while orders or queue:
	while orders and orders[0][0] <= time_elapsed:
		(entered, duration) = heappop(orders)
		heappush(queue, (duration, entered))
	if not queue:
		(entered, duration) = heappop(orders)
		time_elapsed = entered
		heappush(queue, (duration, entered))
	(cook_duration, cook_entered_time) = heappop(queue)
	wait_time = time_elapsed - cook_entered_time
	time_elapsed += cook_duration
	wait_time += cook_duration
	wait_times.append(wait_time)
print(int(sum(wait_times) / n))


import heapq
N = int(input().strip())
C = []
for _ in range(N):
	(T_i, L_i) = [int(tmp) for tmp in input().strip().split(' ')]
	C.append((T_i, L_i))
C = sorted(C)
H = []
avg = i = j = 0
t = -float('inf')
while True:
	if len(H) == 0 and i < N:
		t = max(t, C[i][0])
	while i < N:
		(T_i, L_i) = C[i]
		if T_i > t:
			break
		heapq.heappush(H, (L_i, T_i))
		i += 1
	if len(H) == 0:
		break
	(L_j, T_j) = heapq.heappop(H)
	j += 1
	t += L_j
	avg = ((j - 1) * avg + t - T_j) / j
print(int(avg))


class MinHeap(object):

	def __init__(self, key_val):
		self.items = [0]
		self.key = key_val

	def __repr__(self):
		return ' '.join(map(str, self.items[1:]))

	def size(self):
		return len(self.items) - 1

	def isEmpty(self):
		return self.size() == 0

	def hasLeftChild(self, idx):
		if 2 * idx <= self.size():
			return True
		return False

	def getLeftChild(self, idx):
		return self.items[2 * idx]

	def hasRightChild(self, idx):
		if 2 * idx + 1 <= self.size():
			return True
		return False

	def getRightChild(self, idx):
		return self.items[2 * idx + 1]

	def buildHeap(self, arr):
		i = len(arr) // 2
		self.items.append(arr)
		while i > 0:
			self.siftDown(i)
			i -= 1

	def insert(self, val):
		self.items.append(val)
		self.siftUp(self.size())

	def siftUp(self, idx):
		while idx // 2 > 0:
			if self.items[idx // 2].get_val(self.key) > self.items[idx].get_val(self.key):
				(self.items[idx], self.items[idx // 2]) = (self.items[idx // 2], self.items[idx])
				idx //= 2
			else:
				break

	def siftDown(self, idx):
		while idx * 2 <= self.size():
			if self.hasRightChild(idx):
				if self.items[idx * 2].get_val(self.key) < self.items[idx * 2 + 1].get_val(self.key):
					minIdx = idx * 2
				else:
					minIdx = idx * 2 + 1
			else:
				minIdx = idx * 2
			if self.items[idx].get_val(self.key) > self.items[minIdx].get_val(self.key):
				(self.items[idx], self.items[minIdx]) = (self.items[minIdx], self.items[idx])
				idx = minIdx
			else:
				break

	def delMin(self):
		minItem = self.items[1]
		(self.items[1], self.items[-1]) = (self.items[-1], self.items[1])
		_ = self.items.pop()
		self.siftDown(1)
		return minItem

	def delete(self, val):
		eleIdx = self.items.index(val)
		self.items[eleIdx] = self.items[-1]
		self.items.pop()
		self.siftDown(eleIdx)

	def getMin(self):
		return self.items[1]

	def sort(self):
		while self.size() > 1:
			(self.items[1], self.items[self.size()]) = (self.items[self.size()], self.items[1])
			self.siftDown(1)
		self.items = [0] + self.items[-1:0:-1]
		return ' '.join(map(str, self.items[1:]))

class Order(object):

	def __init__(self, arrival_t, cook_t):
		self.arrival_time = arrival_t
		self.cooking_time = cook_t
		self.waiting_time = 0

	def processed(self, process_t):
		self.waiting_time = process_t - self.arrival_time + self.cooking_time

	def get_waiting_time(self):
		return self.waiting_time

	def get_arrival_time(self):
		return self.arrival_time

	def get_cooking_time(self):
		return self.cooking_time

	def compare_arrival_time(self, other_order):
		return self.arrival_time <= other_order.arrival_time

	def compare_cooking_time(self, other_order):
		return self.cooking_time <= other_order.cooking_time

	def get_val(self, key):
		if key == 1:
			return self.get_arrival_time()
		else:
			return self.get_cooking_time()

	def __repr__(self):
		return (str(self.get_arrival_time()), str(self.get_cooking_time()))
all_orders = MinHeap(1)
waiting_orders = MinHeap(2)
n = int(input().strip())
total_orders = n
while n:
	(arrival_time, cooking_time) = map(int, input().strip().split(' '))
	all_orders.insert(Order(arrival_time, cooking_time))
	n -= 1
time = 0
total_waiting_time = 0
orders_processed = total_orders
while orders_processed > 0:
	while not all_orders.isEmpty() and all_orders.getMin().get_arrival_time() <= time:
		waiting_orders.insert(all_orders.delMin())
	if waiting_orders.size() > 0:
		processing = waiting_orders.delMin()
		processing.processed(time)
		total_waiting_time += processing.get_waiting_time()
		time += processing.get_cooking_time()
		orders_processed -= 1
	else:
		time = all_orders.getMin().get_arrival_time()
print(total_waiting_time // total_orders)


import heapq
n = int(input())
orders = []
cook_heap = []
wait_time = 0
for _ in range(n):
	order = [int(x) for x in input().split()]
	orders.append(order)
orders.sort()
current_time = orders[0][0]
while orders:
	while orders != [] and orders[0][0] <= current_time:
		heapq.heappush(cook_heap, orders.pop(0)[::-1])
	if cook_heap == []:
		current_time = orders[0][0]
	else:
		ord_up = heapq.heappop(cook_heap)
		current_time += ord_up[0]
		wait_time += current_time - ord_up[1]
while cook_heap:
	ord_up = heapq.heappop(cook_heap)
	current_time += ord_up[0]
	wait_time += current_time - ord_up[1]
print(wait_time // n)


import heapq
n = int(input())
arr = []
for i in range(n):
	a = input().split()
	arr.append([int(i) for i in a])
arr.sort(key=lambda x: x[0])
heapq.heapify(arr)
completion = []
heapq.heapify(completion)

def sol(arr, completion, n):
	t = 0
	waiting = 0
	while len(arr) > 0 or len(completion) > 0:
		while len(arr) > 0:
			if arr[0][0] <= t:
				item = heapq.heappop(arr)
				heapq.heappush(completion, item[::-1])
			else:
				break
		if len(completion) > 0:
			item = heapq.heappop(completion)
			waiting += t + item[0] - item[1]
			t += item[0]
		else:
			t += arr[0][0] - t
	return waiting
wait = sol(arr, completion, n)
avg = float(wait) / float(n)
print(int(avg / 1))


import heapq
import copy

class Customer:

	def __init__(self, i, l):
		self.index = i
		self.arrival = l[0]
		self.cook = l[1]
N = int(input())
h = []
time = [None for _ in range(N)]
Cus_list = []
for i in range(N):
	line = [int(n) for n in input().strip().split()]
	Cus_list.append((line[0], line))
Cus_list.sort()
for i in range(N):
	Cus_list[i] = Customer(i, Cus_list[i][1])
cur_cus = Cus_list[0]
cur_time = 0
finish_time = cur_cus.cook + cur_cus.arrival
if N < 2:
	print(cur_time)
	exit()
nxt_cus = Cus_list[1]
c = 1
while len(h) > 0 or c < N:
	while nxt_cus.arrival <= finish_time and c < N:
		tmp_cus = copy.deepcopy(nxt_cus)
		heapq.heappush(h, ((tmp_cus.cook, tmp_cus.index), tmp_cus))
		c += 1
		if c >= N:
			break
		nxt_cus = Cus_list[c]
	time[cur_cus.index] = finish_time - cur_cus.arrival
	cur_time = finish_time
	if len(h) > 0:
		try:
			cur_cus = heapq.heappop(h)[1]
		except:
			print(h[0])
			assert False
	else:
		cur_cus = copy.deepcopy(nxt_cus)
		if c < N:
			nxt_cus = Cus_list[c]
			c += 1
	finish_time = cur_time + cur_cus.cook
time[cur_cus.index] = finish_time - cur_cus.arrival
print(int(sum(time) / len(time)))


from heapq import heappush, heappop
allOrderHeap = []
queryCountString = input()
queryCount = int(queryCountString)
customerWaitHeap = []
totalCustomers = queryCount
totalWaitingTime = 0
currentTime = 0

def UpdateWaitHeap(currentTime):
	while allOrderHeap[0][0] < currentTime:
		(entryTime, entryCount, runTime) = heappop(allOrderHeap)
		heappush(customerWaitHeap, [runTime, entryCount, entryTime])
		if len(allOrderHeap) == 0:
			break
	if len(customerWaitHeap) == 0:
		(entryTime, entryCount, runTime) = heappop(allOrderHeap)
		heappush(customerWaitHeap, [runTime, entryCount, entryTime])
		currentTime = entryTime
	return currentTime
for q in range(0, queryCount):
	command = [int(x) for x in input().split()]
	entryTime = command[0]
	entryCount = q
	runTime = command[1]
	heappush(allOrderHeap, [entryTime, entryCount, runTime])
while len(allOrderHeap) > 0 or len(customerWaitHeap) > 0:
	if len(allOrderHeap) > 0:
		currentTime = UpdateWaitHeap(currentTime)
	(runTime, entryCount, entryTime) = heappop(customerWaitHeap)
	totalWaitingTime = totalWaitingTime + (currentTime - entryTime + runTime)
	currentTime = currentTime + runTime
print(int(totalWaitingTime / totalCustomers))


from heapq import *
orders = []
queue = []
wait_times = []
time_elapsed = 0
n = int(input().strip())
for i in range(n):
	(time_entered, time_to_complete) = map(int, input().strip().split(' '))
	heappush(orders, (time_entered, time_to_complete))
while orders or queue:
	while orders and orders[0][0] <= time_elapsed:
		(entered, duration) = heappop(orders)
		heappush(queue, (duration, entered))
	if not queue:
		(entered, duration) = heappop(orders)
		time_elapsed = entered
		heappush(queue, (duration, entered))
	(cook_duration, cook_entered_time) = heappop(queue)
	wait_time = time_elapsed - cook_entered_time
	time_elapsed += cook_duration
	wait_time += cook_duration
	wait_times.append(wait_time)
print(int(sum(wait_times) / n))


from heapq import *

class qa:

	def __init__(self):
		self.q = []
		self.x = None

	def pop(self, i=0):
		if i == 0:
			t = self.x
			if len(self.q) > 0:
				self.x = heappop(self.q)
			else:
				self.x = None
			return t
		else:
			return self.q.pop(i - 1)

	def get(self, i):
		if self.x is None:
			return self.q[i]
		elif i > 0:
			return self.q[i - 1]
		else:
			return self.x

	def size(self):
		if self.x is None:
			return len(self.q)
		else:
			return 1 + len(self.q)

	def put(self, v):
		if self.x is None:
			self.x = v
		elif v < self.x:
			heappush(self.q, self.x)
			self.x = v
		else:
			heappush(self.q, v)

	def peek(self):
		return self.x

	def pp(self):
		a = [i for i in self.q]
		a.insert(0, self.x)
		print(a)
a = qa()
b = qa()
n = int(input())
for i in range(n):
	(t, c) = map(int, input().split())
	b.put((t, c, c + 2 * t))
log = False
if log:
	a.pp()
	b.pp()
s = 0.0
t = 0.0
e = []
for i in range(n):
	while b.peek() is not None and b.peek()[0] <= t:
		d = b.pop()
		a.put((d[1], d[0]))
	if a.size() == 0:
		d = b.pop()
		s += d[1]
		t = d[0] + d[1]
	else:
		d = a.pop()
		s += d[0] + t - d[1]
		t += d[0]
	if log:
		print(t)
		a.pp()
		b.pp()
		print('')
if log:
	print('Last')
print(int(s / n))


import heapq as h
N = int(input())
notarrived = []
arrived = []
time = 0
wait = 0
for _ in range(N):
	(t, l) = map(int, input().split())
	h.heappush(notarrived, (t, l))
while notarrived or arrived:
	while notarrived and notarrived[0][0] <= time:
		(t, l) = h.heappop(notarrived)
		h.heappush(arrived, (l, t))
	if not arrived:
		time = notarrived[0][0]
	else:
		(l, t) = h.heappop(arrived)
		time = time + l
		wait = wait + time - t
print(wait // N)


import math

def right(i):
	return 2 * i + 1

def left(i):
	return 2 * i + 2

def parent(i):
	return math.ceil(i / 2) - 1

def heapify(ar, i, ln, compare):
	if i >= ln:
		return
	largest = i
	l = left(i)
	r = right(i)
	if l < ln and compare(ar[l], ar[largest]):
		largest = l
	if r < ln and compare(ar[r], ar[largest]):
		largest = r
	if largest != i:
		temp = ar[i]
		ar[i] = ar[largest]
		ar[largest] = temp
		heapify(ar, largest, ln, compare)

def maxheapify(ar, i, ln):
	return heapify(ar, i, ln, lambda x, y: x > y)

def minheapify(ar, i, ln):
	return heapify(ar, i, ln, lambda x, y: x < y)

def heapsort(ar):
	l = len(ar)
	p = parent(l - 1)
	for i in reversed(range(p + 1)):
		minheapify(ar, i, l)

class Heap:

	def __init__(self, compare, heap=None):
		self.__size = 0
		self.__compare = compare
		if heap == None:
			self.__heap = []
		else:
			self.__heap = heap
			self.__size = len(heap)

	def pop(self):
		if self.isempty():
			raise 'Heap is empty.'
		val = self.__heap[0]
		self.__size -= 1
		if self.__size > 0:
			self.__heap[0] = self.__heap[self.__size]
			heapify(self.__heap, 0, self.__size, self.__compare)
		return val

	def push(self, item):
		if self.__size >= len(self.__heap):
			self.__heap.append(item)
		else:
			self.__heap[self.__size] = item
		i = parent(self.__size)
		self.__size += 1
		while i >= 0:
			heapify(self.__heap, i, self.__size, self.__compare)
			i = parent(i)

	def peek(self):
		return self.__heap[0]

	def isempty(self):
		return self.__size == 0

	def size(self):
		return self.__size

class Order:

	def __init__(self, arrival, cooktime):
		self.arrival = arrival
		self.cooktime = cooktime

def process(orders):
	heap = Heap(lambda x, y: x.cooktime < y.cooktime)
	endtime = orders[0].arrival
	waittime = 0
	i = 0
	while True:
		if not heap.isempty():
			cur = heap.pop()
		elif i < len(orders):
			cur = orders[i]
			i += 1
		else:
			break
		endtime += cur.cooktime
		while i < len(orders) and orders[i].arrival <= endtime:
			heap.push(orders[i])
			i += 1
		waittime += endtime - cur.arrival
	return math.floor(waittime / len(orders))
lines = int(input())
orders = []
for i in range(lines):
	to = input().split(' ')
	orders.append(Order(int(to[0]), int(to[1])))
orders.sort(key=lambda x: x.arrival)
print(process(orders))


from heapq import *
orders = []
queue = []
wait_times = []
time_elapsed = 0
n = int(input().strip())
for i in range(n):
	(time_entered, time_to_complete) = map(int, input().strip().split(' '))
	heappush(orders, (time_entered, time_to_complete))
while orders or queue:
	while orders and orders[0][0] <= time_elapsed:
		(entered, duration) = heappop(orders)
		heappush(queue, (duration, entered))
	if not queue:
		(entered, duration) = heappop(orders)
		time_elapsed = entered
		heappush(queue, (duration, entered))
	(cook_duration, cook_entered_time) = heappop(queue)
	wait_time = time_elapsed - cook_entered_time
	time_elapsed += cook_duration
	wait_time += cook_duration
	wait_times.append(wait_time)
print(int(sum(wait_times) / n))


import heapq

def get_min_avg_time(times):
	num_orders = len(times)
	orders = times
	heapq.heapify(orders)
	queue = []
	waiting_time = 0
	current_time = 0
	while orders or queue:
		while orders and orders[0][0] <= current_time:
			(entered, duration) = heapq.heappop(orders)
			heapq.heappush(queue, (duration, entered))
		if not queue:
			(entered, duration) = heapq.heappop(orders)
			current_time = entered
			heapq.heappush(queue, (duration, entered))
		(duration, entered) = heapq.heappop(queue)
		waiting_time += current_time - entered + duration
		current_time += duration
	return waiting_time // num_orders
n = int(input())
times = []
for _ in range(n):
	(entered, duration) = input().split()
	times.append((int(entered), int(duration)))
print(get_min_avg_time(times))


from heapq import heappush, heappop
n = int(input())
q = []
min_time = 10 ** 10
for _ in range(n):
	(ot, ct) = map(int, input().strip().split())
	q.append((ot, ct))
	if ot < min_time:
		min_time = ot
q = sorted(q, key=lambda x: (x[0], x[1]))
curr_time = min_time
tot_wait_time = 0
h = []
while len(q) > 0 or len(h) > 0:
	i = 0
	while i < len(q):
		if q[i][0] > curr_time:
			break
		i += 1
	for j in range(i):
		c = q.pop(0)
		hc = (c[1], c[0])
		heappush(h, hc)
	if len(h) > 0:
		x = heappop(h)
		curr_time += x[0]
		tot_wait_time += curr_time - x[1]
	else:
		curr_time += 1
print(tot_wait_time // n)