You have a long list of tasks that you need to do today. To accomplish task $i$ you need  $M_i$ minutes, and the deadline for this task is $D_i$. You need not complete a task at a stretch. You can complete a part of it, switch to another task, and then switch back.

You've realized that it might not be possible to complete all the tasks by their deadline. So you decide to do them in such a manner that the maximum amount by which a task's completion time overshoots its deadline is minimized.

Input Format

The first line contains the number of tasks, $\mathbf{T}$. Each of the next $\mathbf{T}$ lines contains two integers, $D_i$ and $M_i$.

Constraints

$1\leq T\leq10^5$ 

$1\leq D_i\leq10^5$ 

$1\leq M_i\leq10^3$  

Output Format

Output $\mathbf{T}$ lines. The $i^{th}$  line contains the value of the maximum amount by which a task's completion time overshoots its deadline, when the first $i$ tasks on your list are scheduled optimally. See the sample input for clarification.

Sample Input
5
2 2
1 1
4 3
10 1
2 1

Sample Output
0  
1  
2  
2  
3

Explanation

The first task alone can be completed in 2 minutes, and so you won't overshoot the deadline. 

With the first two tasks, the optimal schedule can be: 

time 1: task 2 

time 2: task 1  

time 3: task 1

We've overshot task 1 by 1 minute, hence returning 1. 

With the first three tasks, the optimal schedule can be: 

time 1 : task 2 

time 2 : task 1 

time 3 : task 3 

time 4 : task 1 

time 5 : task 3 

time 6 : task 3

Task 1 has a deadline 2, and it finishes at time 4. So it exceeds its deadline by 2. 
Task 2 has a deadline 1, and it finishes at time 1. So it exceeds its deadline by 0.
Task 3 has a deadline 4, and it finishes at time 6. So it exceeds its deadline by 2.  

Thus, the maximum time by which you overshoot a deadline is 2. No schedule can do better than this.

Similar calculation can be done for the case containing 5 tasks.

Source: hackerrank | Difficulty: HARD
Tags: Complete search


Solutions:
def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


from bisect import insort
T = int(input())
tasks = []
maxt = used_time = 0
for _ in range(T):
	task = [int(x) for x in input().split()]
	if maxt and task[0] <= tasks[0][0]:
		used_time += task[1]
		print(max(0, used_time + tasks[0][1] - tasks[0][0]))
		continue
	insort(tasks, task)
	maxt = idx = 0
	t = used_time
	for (i, (td, tm)) in enumerate(tasks):
		t += tm
		if t - td > maxt:
			idx = i
			maxt = t - td
	if maxt:
		for _ in range(idx):
			used_time += tasks.pop(0)[1]
	print(maxt)


class Bit:

	def __init__(self, size):
		self.A = [0 for i in range(size + 1)]
		self.size = size

	def __repr__(self):
		return 'Class %s (size %d)' % (self.__class__.__name__, self.size)

	def __str__(self):
		return str([self.A[i] for i in range(0, len(self.A))])

	def sum(self, idx):
		s = 0
		while idx > 0:
			s += self.A[idx]
			idx -= idx & -idx
		return s

	def update(self, idx, value):
		assert idx > 0
		try:
			while idx < len(self.A):
				self.A[idx] += value
				idx += idx & -idx
		except IndexError:
			print('ARGH: update: Idx = %d' % idx)
ntasks = int(input())
tasks_by_id = []
for i in range(ntasks):
	(d, w) = [int(x) for x in input().split()]
	t = (i + 1, d, w)
	tasks_by_id.append(t)
tasks_by_deadline = sorted(tasks_by_id, key=lambda x: x[1])
bitree = Bit(ntasks)
id2dl = [-1 for i in range(ntasks + 1)]
for (i, t) in enumerate(tasks_by_deadline):
	id2dl[t[0]] = i
idl = lambda t: id2dl[t[0]]
L = []
max_delay = 0
for (i, t) in enumerate(tasks_by_id):
	mybitindex = idl(t) + 1
	bitree.update(mybitindex, t[2])
	if False:
		for j in range(0, i + 1):
			bitindex = id2dl[j + 1] + 1
			if bitindex < mybitindex:
				continue
			deadline = tasks_by_id[j][1]
			ex_complete = bitree.sum(bitindex)
			delta = max(0, ex_complete - deadline)
			if delta > max_delay:
				max_delay = delta
	else:
		deadline = tasks_by_id[i][1]
		ex_complete = bitree.sum(mybitindex)
		overshoot = ex_complete - deadline
		for T in L:
			id = T[0]
			dlid = id2dl[id + 1]
			bitindex = dlid + 1
			if bitindex > mybitindex:
				jdeadline = tasks_by_id[id][1]
				jex_complete = bitree.sum(bitindex)
				T[1] = jex_complete - jdeadline
		L.sort(key=lambda x: x[1], reverse=True)
		ins_ind = 0
		for T in L:
			if overshoot < T[1]:
				ins_ind += 1
			else:
				break
		L.insert(ins_ind, [i, overshoot])
		d = tasks_by_id[L[0][0]][1]
		o = L[0][1]
		for (j, T) in enumerate(L):
			if tasks_by_id[T[0]][1] < d and T[1] <= o:
				del L[j]
	print(max(0, L[0][1]))


import bisect
T = int(input().strip())
QueryList = []
InsertList = []
for i in range(T):
	(D, M) = [int(m) for m in input().strip().split()]
	QueryList.append((D, M))
	InsertList.append((D, M))
InsertList.sort()

class BinTree:

	def __init__(self):
		self.offset = 0
		self.l = None
		self.r = None
		self.IndRng = []

	def BuildTree(self, List, SplitBit=-1, IndRng=None):
		Len = len(List)
		self.IndRng = IndRng
		if IndRng != None:
			self.MidInd = (self.IndRng[0] + self.IndRng[1] + 1) // 2
		else:
			if SplitBit == -1:
				SplitBit = len(format(Len - 1, 'b')) - 1
			self.IndRng = [0, 2 ** (SplitBit + 1) - 1]
			self.MidInd = (self.IndRng[0] + self.IndRng[1] + 1) // 2
		if self.IndRng[1] != self.IndRng[0] + 1:
			SplitInd = 2 ** SplitBit
			self.l = BinTree()
			self.l.BuildTree(List[:SplitInd], SplitBit - 1, [self.IndRng[0], self.IndRng[0] + SplitInd - 1])
			if Len > SplitInd:
				self.r = BinTree()
				self.r.BuildTree(List[SplitInd:], SplitBit - 1, [self.IndRng[0] + SplitInd, self.IndRng[0] + SplitInd * 2 - 1])
			self.UpdateMax()
		elif Len == 2:
			self.l = List[0]
			self.r = List[1]
			self.MaxVal = max([self.l, self.r])
		elif Len == 1:
			self.l = List[0]
			self.MaxVal = self.l

	def UpdateMax(self):
		if self.l == None and self.r == None:
			self.MaxVal = None
		elif self.l == None:
			if self.IndRng[1] == self.IndRng[0] + 1:
				self.MaxVal = self.r + self.offset
			else:
				self.MaxVal = self.r.MaxVal + self.offset
		elif self.r == None:
			if self.IndRng[1] == self.IndRng[0] + 1:
				self.MaxVal = self.l + self.offset
			else:
				self.MaxVal = self.l.MaxVal + self.offset
		elif self.IndRng[1] == self.IndRng[0] + 1:
			self.MaxVal = max([self.l, self.r]) + self.offset
		elif self.l.MaxVal == None and self.r.MaxVal == None:
			self.MaxVal = None
		elif self.l.MaxVal == None:
			self.MaxVal = self.r.MaxVal + self.offset
		elif self.r.MaxVal == None:
			self.MaxVal = self.l.MaxVal + self.offset
		else:
			self.MaxVal = max([self.l.MaxVal, self.r.MaxVal]) + self.offset

	def CullElement(self, Index, UpDateMax=True):
		if self.IndRng[1] != self.IndRng[0] + 1:
			if Index >= self.MidInd:
				self.r.CullElement(Index, UpDateMax)
			else:
				self.l.CullElement(Index, UpDateMax)
		elif Index == self.IndRng[0]:
			self.l = None
		elif Index == self.IndRng[1]:
			self.r = None
		if self.IndRng[1] != self.IndRng[0] + 1:
			if self.l != None:
				if self.l.l == None and self.l.r == None:
					self.l = None
			if self.r != None:
				if self.r.l == None and self.r.r == None:
					self.r = None
		if UpDateMax:
			self.UpdateMax()

	def PropagateValue(self, Index, PropValue):
		if self.IndRng[1] >= Index:
			if self.IndRng[0] >= Index:
				self.offset -= PropValue
			elif self.IndRng[1] == self.IndRng[0] + 1:
				if Index == self.IndRng[0] and self.l != None:
					self.l -= PropValue
				elif Index == self.IndRng[1] and self.r != None:
					self.r -= PropValue
			else:
				if self.l != None:
					self.l.PropagateValue(Index, PropValue)
				if self.r != None:
					self.r.PropagateValue(Index, PropValue)
		self.UpdateMax()

	def CullAndProp(self, Index, PropValue):
		self.CullElement(Index, False)
		self.PropagateValue(Index, PropValue)
for I in range(T):
	InsertList[I] += (I,)
CS = 0
DiffList = []
for i in InsertList:
	CS += i[1]
	DiffList.append(CS - i[0])
Tree = BinTree()
Tree.BuildTree(DiffList)
MaxValList = [Tree.MaxVal]
for q in QueryList[::-1][:-1]:
	SearchTup = q + (0,)
	LocInd = bisect.bisect_left(InsertList, SearchTup)
	TaskRemoved = InsertList[LocInd]
	del InsertList[LocInd]
	Tree.CullAndProp(TaskRemoved[2], TaskRemoved[1])
	MaxValList.append(max([Tree.MaxVal, 0]))
for i in MaxValList[::-1]:
	print(i)


import math

def slow(L):
	n = len(L)
	L.sort()
	(D, M) = zip(*L)
	i = 0
	dum = 0
	for lexa in range(n):
		dum = max(dum, i + M[lexa] - D[lexa])
		i += M[lexa]
	print(dum)
n = int(input())
L = []
for _ in range(n):
	L.append(tuple((int(x) for x in input().split())))
nth_place = sorted(list(range(n)), key=lambda x: L[x])
nth_task = [0] * n
for i in range(n):
	nth_task[nth_place[i]] = i
L.sort()
(D, M) = zip(*L)
data = [-d for d in D]
n = 2 ** math.ceil(math.log2(n))
relmax = [0] * (2 * n)
offset = [0] * (2 * n)

def add(a, ind):
	treeind = n + ind
	offset[treeind] += a
	while treeind > 0:
		if treeind % 2 == 1:
			offset[treeind - 1] += a
		treeind //= 2
	treeind = (n + ind) // 2
	while treeind > 0:
		relmax[treeind] = max(relmax[treeind * 2] + offset[treeind * 2], relmax[treeind * 2 + 1] + offset[treeind * 2 + 1])
		treeind //= 2

def maxim():
	return offset[1] + relmax[1]
for (i, d) in enumerate(data):
	relmax[i + n] = d
for i in range(n - 1, 0, -1):
	relmax[i] = max(relmax[i * 2], relmax[i * 2 + 1])
for i in range(len(data)):
	dataind = nth_task[i]
	mi = M[nth_task[i]]
	add(mi, len(data) - 1)
	if dataind > 0:
		add(-mi, dataind - 1)
	print(max(0, maxim()))


import bisect
n = int(input().strip())
deadlines_sorted_list = []
overtime = 0
max_index = 0
for i in range(n):
	task = list(map(int, input().strip().split(' ')))
	duration = task[1]
	deadline = task[0]
	index = bisect.bisect_left(deadlines_sorted_list, [deadline, duration, 0])
	if not deadlines_sorted_list:
		deadlines_sorted_list.append([deadline, duration, duration])
		overtime = max(overtime, duration - deadline)
	elif index == len(deadlines_sorted_list):
		new_tot = deadlines_sorted_list[index - 1][2] + duration
		deadlines_sorted_list.insert(index, [deadline, duration, new_tot])
		if new_tot - deadline > overtime:
			deadlines_sorted_list = [deadlines_sorted_list[-1]]
			max_index = 0
			overtime = new_tot - deadline
	else:
		if index == 0:
			deadlines_sorted_list.insert(index, [deadline, duration, 0])
		else:
			deadlines_sorted_list.insert(index, [deadline, duration, deadlines_sorted_list[index - 1][2]])
		for j in range(index, len(deadlines_sorted_list)):
			deadlines_sorted_list[j][2] += duration
			if deadlines_sorted_list[j][2] - deadlines_sorted_list[j][0] >= overtime:
				overtime = deadlines_sorted_list[j][2] - deadlines_sorted_list[j][0]
				max_index = j
		deadlines_sorted_list = deadlines_sorted_list[max_index:]
		max_index = 0
	print(overtime)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def update_tree(id, l, r, u, v, val):
	if v < l or u > r:
		return
	if u <= l and r <= v:
		tree[id][0] += val
		tree[id][1] += val
		return
	mid = (l + r) // 2
	tree[id * 2][0] += tree[id][1]
	tree[id * 2][1] += tree[id][1]
	tree[id * 2 + 1][0] += tree[id][1]
	tree[id * 2 + 1][1] += tree[id][1]
	tree[id][1] = 0
	update_tree(id * 2, l, mid, u, v, val)
	update_tree(id * 2 + 1, mid + 1, r, u, v, val)
	tree[id][0] = max(tree[id * 2][0], tree[id * 2 + 1][0])

def get(id, l, r, u, v):
	if v < l or u > r:
		return -1
	if u <= l and r <= v:
		return tree[id][0]
	mid = (l + r) // 2
	tree[id * 2][0] += tree[id][1]
	tree[id * 2][1] += tree[id][1]
	tree[id * 2 + 1][0] += tree[id][1]
	tree[id * 2 + 1][1] += tree[id][1]
	tree[id][1] = 0
	return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v))
n = int(input())
tasks = []
rank = [0] * n
used = [0 for i in range(n)]
tree = []
for i in range(4 * n):
	tree.append([0, 0])
for i in range(n):
	s = input().split(' ')
	tasks.append([i, int(s[0]), int(s[1])])
tasks.sort(key=lambda pair: pair[1])
for i in range(n):
	rank[tasks[i][0]] = i
tasks.sort(key=lambda pair: pair[0])
for i in range(n):
	update_tree(1, 0, n - 1, rank[i], rank[i], -tasks[i][1])
for i in range(n):
	update_tree(1, 0, n - 1, rank[i], n - 1, tasks[i][2])
	print(max(get(1, 0, n - 1, 0, n - 1), 0))


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import os
import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


import math
import os
import random
import re
import sys
import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


import math
import os
import random
import re
import sys
import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import math
import os
import random
import re
import sys
import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import math
import os
import random
import re
import sys

def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


def return_index(lst, num):
	if not lst:
		return None
	if len(lst) == 1:
		if num > lst[0]:
			return 0
		else:
			return None
	start = 0
	end = len(lst) - 1
	return binary_search(lst, num, start, end)

def binary_search(lst, num, start, end):
	if start == end:
		if num >= lst[start]:
			return start
		else:
			return start - 1
	else:
		mid = (end - start) // 2 + start
		if num > lst[mid]:
			return binary_search(lst, num, mid + 1, end)
		elif num < lst[mid]:
			return binary_search(lst, num, start, mid)
		else:
			return mid

def task_scheduling(length, lst, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			lst.append(i + length)
		length = deadline
	minLeft = minutes
	idx = return_index(lst, deadline - 1)
	if idx != None:
		while idx >= 0 and minLeft > 0:
			lst.pop(idx)
			idx -= 1
			minLeft -= 1
	while minLeft > 0 and lst and (lst[0] < deadline):
		lst.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
lst = []
late = 0
for i in range(n):
	task = input().split(' ')
	(late, length) = task_scheduling(length, lst, int(task[0]), int(task[1]), late)
	print(late)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)


import sys

class tree:
	__slots__ = ('left', 'right', 'free', 'size')

	def __init__(self, size=2):
		if size == 0:
			return None
		if size > 1:
			half = size // 2
			self.left = tree(size - half)
			self.right = tree(half)
		else:
			self.left = self.right = None
		self.free = size
		self.size = size

	def resize(self, n):
		while self.size < n:
			t = tree(0)
			t.left = self
			t.right = tree(self.size)
			t.free = t.left.size + t.right.size
			t.size = self.size * 2
			self = t
		return self

	def recfill(self, dur, end):
		if dur == 0:
			return 0
		if self.free == 0:
			return 0
		if self.size <= dur and dur <= end or self.size == 1:
			r = self.free
			self.free = 0
			return r
		r = 0
		if self.left.size < end:
			r += self.right.recfill(dur, end - self.left.size)
		r += self.left.recfill(dur - r, end)
		self.free -= r
		return r
t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
	two_strings = sys.stdin.readline().strip().split(' ')
	(end, dur) = (int(i) for i in two_strings)
	t = t.resize(end)
	b = t.recfill(dur, end)
	r = r + dur - b
	print(r)


def returnIndex(array, number):
	if not array:
		return None
	if len(array) == 1:
		if number > array[0]:
			return 0
		else:
			return None
	si = 0
	ei = len(array) - 1
	return binarySearch(array, number, si, ei)

def binarySearch(array, number, si, ei):
	if si == ei:
		if number >= array[si]:
			return si
		else:
			return si - 1
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearch(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearch(array, number, si, middle)
		else:
			return middle

def addJob(length, array, deadline, minutes, late):
	if length < deadline:
		for i in range(deadline - length):
			array.append(i + length)
		length = deadline
	minLeft = minutes
	index = returnIndex(array, deadline - 1)
	if index != None:
		while index >= 0 and minLeft > 0:
			array.pop(index)
			index -= 1
			minLeft -= 1
	while minLeft > 0 and array and (array[0] < deadline):
		array.pop(0)
		minLeft -= 1
	late += minLeft
	return (late, length)
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
	job = input().split(' ')
	(late, length) = addJob(length, nl, int(job[0]), int(job[1]), late)
	print(late)