Suppose there is a circle. There are $N$ petrol pumps on that circle. Petrol pumps are numbered $\mbox{0}$ to $(N-1)$ (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. 

Initially, you have a tank of infinite capacity carrying no petrol. You can start the tour at any of the petrol pumps. Calculate the first point from where the truck will be able to complete the circle. Consider that the truck will stop at each of the petrol pumps. The truck will move one kilometer for each litre of the petrol.

Input Format

The first line will contain the value of $N$.

The next $N$ lines will contain a pair of integers each, i.e. the amount of petrol that petrol pump will give and the distance between that petrol pump and the next petrol pump.

Constraints:

$1\leq N\leq10^5$

$1\leq\text{amount of petrol},\text{distance}\leq10^9$

Output Format

An integer which will be the smallest index of the petrol pump from which we can start the tour.

Sample Input
3
1 5
10 3
3 4

Sample Output
1

Explanation

We can start the tour from the second petrol pump.

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

Starter code:

Solutions:
N = int(input())
(s, c) = (0, 0)
for i in range(N):
	(p, d) = (int(_) for _ in input().split())
	if c + p < d:
		s = i + 1
		c = 0
	else:
		c += p - d
print(s)


n = int(input())
endurance = []
for _ in range(n):
	(fuel, distance) = [int(x) for x in input().split()]
	endurance.append(fuel - distance)
lo = hi = 0
total_endurance = 0
while hi - lo < n:
	if total_endurance + endurance[hi % n] > 0:
		total_endurance += endurance[hi % n]
		hi += 1
	else:
		total_endurance = 0
		hi += 1
		lo = hi
print(lo)


def where_can_i_start(pump_list):
	min_balance = 9999999
	i = 0
	position = 0
	balance = 0
	while i < len(pump_list):
		balance += pump_list[i][0] - pump_list[i][1]
		if balance < min_balance:
			min_balance = balance
			position = (i + 1) % len(pump_list)
		i += 1
	return position
pump_list = []
num_pumps = int(input())
for i in range(0, num_pumps):
	pump_list.append([int(numeric_string) for numeric_string in input().split()])
print(where_can_i_start(pump_list))


tests = int(input())
pumps = []
for test in range(0, tests):
	pumps.append(list(map(int, input().split(' '))))
currGallons = 0
for currPumpIndex in range(0, len(pumps)):
	for index in range(0, len(pumps)):
		(gals, dist) = pumps[(currPumpIndex + index) % len(pumps)]
		currGallons = currGallons + gals
		if currGallons >= dist:
			currGallons -= dist
		else:
			currGallons = 0
			break
	else:
		print(currPumpIndex)
		break


import fileinput
station_list = []
index = 0
prev = 0
for line in fileinput.input():
	if fileinput.isfirstline():
		n_pump = int(line.rstrip())
	else:
		(gas, dist) = [int(x) for x in line.rstrip().split(' ')]
		station_list += [gas - dist + prev]
		prev = gas - dist + prev
		index += 1
min_value = station_list[0]
min_index = 0
for x in range(1, n_pump):
	if station_list[x] < min_value:
		min_value = station_list[x]
		min_index = x
print((min_index + 1) % n_pump)


import sys
N = int(sys.stdin.readline())
stations = []
for station in range(N):
	stations.append(tuple([int(X) for X in sys.stdin.readline().split()]))
tank = 0
start = 0
position = 0
for (petrol, distance) in stations:
	position += 1
	if tank + petrol < distance:
		start = position
		tank = 0
	else:
		tank += petrol - distance
print(start)


pumps = [[int(j) for j in input().split()] for i in range(int(input()))]
pumps = [i[0] - i[1] for i in pumps]
total = sum(pumps)
m = 0
c = 0
for i in pumps:
	c += i
	m = min(m, c)
if m > 0:
	print(0)
for i in range(len(pumps)):
	m = min(m - pumps[i], total - pumps[i])
	if m >= 0:
		print(i + 1)
		break


n = int(input())
f = [0] * n
d = [0] * n
q = [0] * n
running = 0
index = 0
for i in range(0, n):
	if running == 0:
		index = i
	(a, b) = input().split()
	(f[i], d[i]) = (int(a), int(b))
	q[i] = f[i] - d[i]
	if running + q[i] >= 0:
		running += q[i]
	else:
		running = 0
print(index)


n = int(input())

def convert(group):
	return [int(group[0]), int(group[1])]
nums = [convert(input().split(' ')) for i in range(n)]

def find():
	i = 0
	wrap = False
	while i < n:
		total = 0
		j = i
		while total >= 0:
			total += nums[j][0]
			total -= nums[j][1]
			if total < 0:
				if wrap:
					return -1
				i = j + 1
				break
			j = (j + 1) % n
			if i == j:
				return i
			if j == 0:
				wrap = True
	return -1
if n == 0:
	print(-1)
else:
	print(find())


n = input()
stations = []
possibilities = set()
for i in range(int(n)):
	(fuel, dist) = input().split()
	stations.insert(0, (int(fuel), int(dist)))
total = 0
smallest_index = int(n)
smallest_total = stations[0][0]
for i in range(int(n)):
	(fuel, dist) = stations.pop()
	total += fuel
	total -= dist
	if total <= smallest_total:
		smallest_total = total
		smallest_index = i + 1
print(smallest_index)


N = int(input())
P = []
for i in range(N):
	P.append(tuple([int(x) for x in input().split()]))
tank = 0
start = 0
position = 0
for (petrol, distance) in P:
	position += 1
	if tank + petrol < distance:
		start = position
		tank = 0
	else:
		tank += petrol - distance
print(start)


num = int(input())
pet = []
dist = []
for line in range(num):
	i = input().split(' ')
	pet.append(int(i[0]))
	dist.append(int(i[1]))
bal = []
for i in range(num):
	bal.append(pet[i] - dist[i])
small = 0
for strt in range(num):
	s = bal[strt]
	i = (strt + 1) % num
	while s >= 0 and i != strt:
		s += bal[i]
		i = (i + 1) % num
	if i == strt:
		small = strt
		break
print(small)


from itertools import cycle
from sys import exit
no_pumbs = int(input())
pumb_list = []
for i in range(no_pumbs):
	(a, b) = input().split()
	pumb_list.append((int(a), int(b)))
for (i, pumb) in enumerate(pumb_list):
	if pumb[0] < pumb[1]:
		continue
	else:
		tank = pumb[0]
		distance = pumb[1]
		start_index = j = i
		start_pumb = pumb
		while True:
			j = (j + 1) % no_pumbs
			if j == start_index:
				print(j)
				exit(0)
			tank = tank - distance + pumb_list[j][0]
			distance = pumb_list[j][1]
			if tank < distance:
				break


def next_idx(idx, n):
	if idx < n - 1:
		idx += 1
	else:
		idx = 0
	return idx

def find_pos(capacity_arr, idx):
	ctr = 0
	while ctr < len(capacity_arr):
		ctr += 1
		if capacity_arr[idx] >= 0:
			return idx
		idx = next_idx(idx, len(capacity_arr))
	return -1
n = int(input())
if n == 1:
	print(0)
amt = []
dist = []
cap = []
for i in range(n):
	(a, d) = [int(x) for x in input().split()]
	amt.append(a)
	dist.append(d)
	cap.append(a - d)
curr_cap_idx = find_pos(cap, 0)
curr_cap = cap[curr_cap_idx]
i = next_idx(curr_cap_idx, n)
sp = None
while i != curr_cap_idx:
	if curr_cap + cap[i] < 0:
		curr_cap_idx = find_pos(cap, i)
		curr_cap = cap[curr_cap_idx]
		sp = None
		i = next_idx(curr_cap_idx, n)
	else:
		curr_cap += cap[i]
		if sp == None:
			sp = curr_cap_idx
		i = next_idx(i, n)
print(sp)


from collections import namedtuple

def max_dist(fuel, mileage):
	return fuel * mileage

def fuel_consumed(dist, mileage):
	return dist // mileage
N = int(input())
mileage = 1
Pump = namedtuple('Pump', ['amt', 'dist'])
not_possible = []
pumps = []
for i in range(N):
	pumps.append(Pump(*[int(num) for num in input().split(' ')]))
start = i = 0
current_fuel = 0
while True:
	current_fuel += pumps[i].amt
	if max_dist(current_fuel, mileage) >= pumps[i].dist:
		current_fuel -= fuel_consumed(pumps[i].dist, mileage)
		i += 1
		i %= N
		if i == start:
			print(start)
			break
	else:
		i += 1
		not_possible += range(start, i)
		start = i
		current_fuel = 0
		if start in not_possible:
			break


size = int(input().strip())
p = 0
mini = 0
index = 0
for i in range(0, size):
	line = input().strip().split(' ')
	p += int(line[0])
	p -= int(line[1])
	if p < mini:
		mini = p
		index = i
print(index + 1)


N = int(input())
p_d = []
for _ in range(N):
	(a, b) = map(int, input().split(' '))
	p_d.append(a - b)
sumi = 0
maxi = 0
j = 0
for i in range(N):
	sumi += p_d[i]
	if sumi < 0:
		sumi = 0
		j = i + 1
print(j)


size = int(input())
data = []
for _ in range(size):
	(p, d) = list(map(int, input().split(' ')))
	data.append((p, d))

def try_from(ith):
	reserves = 0
	for i in range(size):
		(p, d) = data[(ith + i) % size]
		reserves += p - d
		if reserves < 0:
			return False
	return True
for i in range(size):
	if try_from(i):
		print(i)
		break


N = int(input())
petrol = []
distance = []
for i in range(N):
	[p, d] = map(int, input().split())
	petrol.append(p)
	distance.append(d)
balance = 0
covered = 0
index = 0
while covered < N:
	while balance >= 0 and covered < N:
		balance = balance + petrol[index % N] - distance[index % N]
		covered += 1
		index += 1
	if balance < 0:
		balance = 0
		covered = 0
	elif covered >= N:
		print(index % N)


class solution:

	def startFrom(self, petrols, miles):
		n = len(petrols)
		if n < 1:
			return -1
		rest = minVal = petrols[0] - miles[0]
		minStart = 0
		for i in range(1, n):
			rest += petrols[i] - miles[i]
			if rest < minVal:
				minVal = rest
				minStart = i
		return (minStart + 1) % n
n = int(input())
petrols = [0] * n
miles = [0] * n
for i in range(n):
	(petrols[i], miles[i]) = [int(x) for x in input().split(' ')]
sol = solution()
ret = sol.startFrom(petrols, miles)
print(ret)


n = int(input().strip())
(start_index, current_usage) = (0, 0)
for i in range(n):
	(petrol, distance) = map(int, input().strip().split())
	if current_usage < 0:
		start_index = i
		current_usage = 0
	current_usage = current_usage + petrol - distance
print(start_index)


n = int(input())
lis = []
for _ in range(n):
	(a, b) = list(map(int, input().split()))
	lis.append(a - b)
res = -1
s = 0
for (i, x) in enumerate(lis):
	s += x
	if s < 0:
		s = 0
		res = (i + 1) % n
print(res)


import sys

def main():
	n = int(input())
	minLocation = -1
	minValue = sys.maxsize
	cur = 0
	for i in range(n):
		[a, b] = [int(val) for val in input().split()]
		cur += a
		cur -= b
		if cur < minValue:
			minValue = cur
			minLocation = i + 1
	if minLocation == n:
		minLocation = 0
	print(str(minLocation))
main()


from collections import deque
n = int(input())
pumps = deque([])
for i in range(n):
	petrol_dist = tuple(map(int, input().split()))
	pumps.append(petrol_dist)
(stops, curr_petrol) = (0, 0)
(i, idx) = (0, 0)
while True:
	if stops >= n:
		break
	(petrol, dist) = pumps.popleft()
	pumps.append((petrol, dist))
	if curr_petrol + petrol >= dist or stops == n - 1:
		if not idx:
			idx = i
		stops += 1
		curr_petrol = curr_petrol + petrol - dist
	else:
		idx = 0
		stops = 0
		curr_petrol = 0
	i += 1
print(idx)


N = int(input())
min_seen = 0
min_loc = 0
petrol = 0
for n in range(1, N):
	(p, d) = [int(x) for x in input().split()]
	petrol = petrol + p - d
	if petrol < min_seen:
		min_seen = petrol
		min_loc = n
print(min_loc)


n = int(input())
pump = [(0, 0)] * n
for i in range(0, n):
	pump[i] = tuple(map(int, input().split()))
cumulative = []
current_petrol = 0
for (petrol, distance) in pump:
	current_petrol += petrol - distance
	cumulative.append(current_petrol)
print(cumulative.index(min(cumulative)) + 1)


startind = 0
gas = 0
for i in range(int(input())):
	line = input().split()
	oil = int(line[0])
	dist = int(line[1])
	if dist > gas + oil:
		startind = i + 1
		gas = 0
		continue
	gas = gas + oil - dist
print(startind)


from collections import deque
d = deque()
inputLength = int(input())
inputData = []
for index in range(inputLength):
	rawData = input().split()
	inputData.append([int(rawData[0]), int(rawData[1]), index])
for data in inputData:
	d.append(data)
while True:
	totalP = 0
	totalD = 0
	petrol = 0
	index = -1
	for i in range(len(d)):
		p = d.popleft()
		petrol += p[0] - p[1]
		totalP += p[0]
		totalD += p[1]
		if index == -1:
			index = p[2]
		if petrol < 0:
			break
	if len(d) > 0:
		index = -1
		d.append([totalP, totalD, 0])
	else:
		print(index)
		break


from collections import deque
n = int(input())
tour = deque()
shortest_index = None
PETROL = 0
DISTANCE = 1
INDEX = 2
for i in range(n):
	the_input = [int(i) for i in input().split()]
	the_input.append(i)
	tour.append(the_input)
while True:
	current = tour.popleft()
	if len(tour) > 0:
		next_point = tour.popleft()
	else:
		break
	(current_petrol, current_distance) = (current[PETROL], current[DISTANCE])
	(next_petrol, next_distance) = (next_point[PETROL], next_point[DISTANCE])
	if current_petrol - current_distance > 0 and current_petrol + next_petrol - (current_distance + next_distance) > 0:
		current[PETROL] += next_petrol
		current[DISTANCE] += next_distance
		tour.appendleft(current)
	else:
		tour.append(current)
		tour.appendleft(next_point)
print(current[INDEX])


from queue import *
n = int(input())
distance = minimum_fuel = starting_point = current_fuel = 0
q = Queue()
for i in range(0, n):
	pump = [i]
	pump.append([int(x) for x in input().split(' ')])
	q.put(pump)
while not q.empty():
	pump = q.get()
	current_fuel -= distance
	if current_fuel < minimum_fuel:
		minimum_fuel = current_fuel
		starting_point = pump[0]
	current_fuel += pump[1][0]
	distance = pump[1][1]
print(starting_point)


n = int(input())
l = []
d = []
for i in range(n):
	(a, b) = map(int, input().split())
	l.append(a)
	d.append(b)
for i in range(len(l)):
	f = 0
	flag = True
	for j in range(i, i + n):
		j %= n
		f += l[j] - d[j]
		if f < 0:
			flag = False
			break
	if flag:
		print(i)
		break


N = int(input())
station_net = []
for i in range(N):
	line = input().split()
	station_net.append(int(line[0]) - int(line[1]))
gas_sum = []
current_sum = 0
min_sum = station_net[0]
for station in station_net:
	current_sum += station
	gas_sum.append(current_sum)
	if current_sum < min_sum:
		min_sum = current_sum
for i in range(N):
	if min_sum >= 0:
		print(i)
		break
	min_sum = min_sum - station_net[i]


import sys

class Node(object):

	def __init__(self, idx, leftover):
		self.idx = idx
		self.leftover = leftover
		self.next = None

	def append(self, node):
		self.next = node

def read_leftover(line):
	tokens = line.split()
	return int(tokens[0]) - int(tokens[1])
n = int(sys.stdin.readline())
if n > 0:
	first = Node(0, read_leftover(sys.stdin.readline()))
if n > 1:
	current = first
	current_idx = 0
	for line in sys.stdin:
		current.next = Node(current_idx + 1, read_leftover(line))
		current_idx += 1
		current = current.next
	current.next = first
start = -1
i = 0
passed = 0
current = first
sum = 0
while passed < n and i < 2 * n:
	if sum + current.leftover < 0:
		start = -1
		sum = 0
		passed = 0
	else:
		sum += current.leftover
		passed += 1
		if start == -1:
			start = current.idx
	current = current.next
	i += 1
print(start)


i = int(input())
stops = []
for x in range(i):
	inp = input().split(' ')
	stops.append(int(inp[0]) - int(inp[1]))

def try_start(s):
	x = 0
	sum = 0
	while x < i:
		sum += stops[(s + x) % i]
		if sum <= 0:
			return 0
		x += 1
	return 1
for trial in range(i):
	if try_start(trial) == 1:
		print(trial)
		break


import sys
data = sys.stdin.readlines()
N = int(data[0])
fuelSums = list()
for i in range(0, N):
	line = data[i + 1]
	petrol = int(line.split()[0])
	dist = int(line.split()[1])
	if i > 0:
		fuelSums.append(fuelSums[i - 1] + petrol - dist)
	else:
		fuelSums.append(petrol - dist)
minInd = fuelSums.index(min(fuelSums))
if minInd == N - 1:
	print('0')
else:
	print(minInd + 1)


from collections import deque
n = int(input())
s = 0
d = 0
start = 0
for x in range(n):
	[a, b] = [int(x) for x in input().strip().split(' ')]
	c = a - b
	s += c
	if s < 0:
		d = s
		s = 0
		start = x + 1
print(start)


N = int(input())
sumi = 0
maxi = 0
j = 0
for i in range(N):
	(a, b) = input().split()
	sumi += int(a) - int(b)
	if sumi < 0:
		sumi = 0
		j = i + 1
print(j)


a = []
for i in range(int(input())):
	a.append(list(map(int, input().split())))
	a[i] = a[i][0] - a[i][1]
sum = 0
fin = 0
shift = 0
while fin < len(a):
	sum += a[fin]
	if sum < 0:
		for _ in range(fin + 1):
			a.append(a.pop(0))
		sum = 0
		shift += fin + 1
		fin = 0
	else:
		fin = fin + 1
print(shift)


__author__ = 'siddharth'
from itertools import cycle
N = int(input())
trucks = []
for _ in range(N):
	(A, B) = map(int, input().split())
	trucks.append(A - B)
trucks = enumerate(trucks)
(marker, tank) = (-1, 0)
for (i, v) in cycle(trucks):
	tank += v
	if marker == i:
		print(marker)
		break
	elif tank < 0:
		tank = 0
		marker = -1
	elif marker == -1 and tank >= 0:
		tank = v
		marker = i


N = int(input())
sumi = 0
maxi = 0
j = 0
for i in range(N):
	(a, b) = input().split()
	sumi += int(a) - int(b)
	if sumi < 0:
		sumi = 0
		j = i + 1
print(j)


numbpumps = int(input())
details = [None] * numbpumps
difference = [None] * numbpumps
for i in range(numbpumps):
	details[i] = input().split()
	difference[i] = int(details[i][0]) - int(details[i][1])
i = 0
j = 0
done = 1
localsum = 0
looped = i
flag1 = 0
while done:
	localsum = difference[i] + localsum
	if looped + i - j + 1 == numbpumps and localsum > 0:
		done = 0
		if flag1 == 0:
			print(i)
		else:
			print(numbpumps - i - 1)
		break
	while localsum < 0:
		localsum = localsum - difference[j]
		if j < numbpumps - 1:
			j = j + 1
		else:
			rak = numbpumps
			while rak:
				difference[rak] = int(details[rak][0]) - int(details[i - 1][1])
			difference.reverse()
			flag1 = 1
	if i < numbpumps - 1:
		i = i + 1
	else:
		i = 0
		looped = numbpumps - 1


n = int(input())
fuel_per_stop = []
fuel = 0
for i in range(n):
	pump = input().split(' ')
	fuel += int(pump[0]) - int(pump[1])
	fuel_per_stop.append(fuel)
print(fuel_per_stop.index(min(fuel_per_stop)) + 1)


n_pumps = int(input())
min_gas = 0
min_pump = 0
gas = 0
for i in range(1, n_pumps):
	(p, d) = map(int, input().split())
	gas += p - d
	if gas < min_gas:
		min_gas = gas
		min_pump = i
print(min_pump)


def load_pumps():
	pumps_queue = list()
	for i in range(int(input())):
		pumps_queue.append(tuple(map(int, input().split())))
	return pumps_queue

def drive_the_truck(pumps_queue):
	start_index = 0
	end_index = 1
	current_petrol = pumps_queue[start_index][0] - pumps_queue[start_index][1]
	while start_index != end_index or current_petrol < 0:
		while current_petrol < 0 and start_index != end_index:
			current_petrol -= pumps_queue[start_index][0] - pumps_queue[start_index][1]
			start_index = (start_index + 1) % len(pumps_queue)
			if start_index == 0:
				return -1
		current_petrol += pumps_queue[end_index][0] - pumps_queue[end_index][1]
		end_index = (end_index + 1) % len(pumps_queue)
	return start_index
pumps_queue = load_pumps()
print(drive_the_truck(pumps_queue))


N = int(input())
pd_list = []
for _ in range(N):
	pd_list.append(tuple([int(x) for x in input().split()]))
fuel_in_tank = [0]
for (p, d) in pd_list:
	fuel_in_tank.append(fuel_in_tank[-1] + p - d)
print(fuel_in_tank.index(min(fuel_in_tank)))


import collections
f = lambda e: e[0] - e[1]
n = int(input())
l = [None] * n
for i in range(n):
	(x, y) = map(int, input().split())
	l[i] = x - y
l += l
j = 0
k = 0
s = 0
for i in range(2 * n):
	if j == n:
		break
	if l[i] + s >= 0:
		j += 1
		s += l[i]
	else:
		j = 0
		s = 0
		k = i + 1
print(k)


n = int(input())
n1 = n
l = []
while n > 0:
	n -= 1
	(x, y) = map(int, input().split())
	l.append(x - y)
sum1 = 0
i = 0
flag = 0
while i < n1:
	j = 0
	sum1 = 0
	while j < n1:
		sum1 += l[(i + j) % n1]
		if sum1 < 0:
			break
		if j == n1 - 1:
			flag = 1
			break
		j += 1
	if flag == 1:
		break
	i += 1
print(i)


n = int(input())
a = []
b = []
while n:
	(x, y) = input().split()
	a.append(int(x))
	b.append(int(y))
	n -= 1
i = 0
n = len(a)
flag = 0
while i != n:
	s1 = 0
	s2 = 0
	flag = 0
	for j in range(i, n):
		s1 += a[j]
		s2 += b[j]
		if s1 < s2:
			i += 1
			flag = 1
			break
	if not flag:
		for j in range(0, i):
			s1 += a[j]
			s2 += b[j]
			if s1 < s2:
				i += 1
				flag = 1
				break
	if flag:
		continue
	else:
		break
print(i)


sumi = 0
maxi = 0
j = 0
for i in range(int(input())):
	(a, b) = list(map(int, input().split()))
	sumi += a - b
	if sumi < 0:
		sumi = 0
		j = i + 1
print(j)


import sys
number_of_petrol_bunks = int(input())
petrol_bunks_details = [[int(element) for element in sys.stdin.readline().split()[0:2]] for i in range(number_of_petrol_bunks)]
petrol_bunk_index = 0
while petrol_bunk_index < number_of_petrol_bunks:
	petrol_tank = 0
	for index in range(petrol_bunk_index, number_of_petrol_bunks + petrol_bunk_index):
		if index >= number_of_petrol_bunks:
			index = index % number_of_petrol_bunks
		petrol_tank += petrol_bunks_details[index][0]
		if petrol_tank >= petrol_bunks_details[index][1]:
			petrol_tank -= petrol_bunks_details[index][1]
		else:
			petrol_bunk_index = index + 1
			break
	else:
		print(petrol_bunk_index)
		break


n = int(input())
a = []
s = 0
for i in range(n):
	a.append(s)
	c = [int(x) for x in input().split()]
	s += c[0] - c[1]
m = min(a)
for i in range(n):
	if a[i] == m:
		print(i)
		break


stations = int(input())
pumps = []
for station in range(stations):
	temp = input().split(' ')
	pumps.append(int(temp[0]) - int(temp[1]))
length_pumps = len(pumps)
start = 0
current = 0
sum = pumps[current]
current = (current + 1) % length_pumps
while current != start:
	if sum < 0:
		start = current
		sum = pumps[current]
	else:
		sum += pumps[current]
	current = (current + 1) % length_pumps
print(start)


N = int(input())
sumi = 0
maxi = 0
j = 0
for i in range(N):
	(a, b) = map(int, input().split())
	sumi += a - b
	if sumi < 0:
		sumi = 0
		j = i + 1
print(j)


n = int(input())
sum_f = 0
answer = -1
for i in range(n):
	(f, d) = [int(x) for x in input().split()]
	sum_f += f - d
	if sum_f < 0:
		sum_f = 0
		answer = i + 1
print(answer)


N = int(input())
sumi = 0
maxi = 0
j = 0
for i in range(N):
	(a, b) = input().split()
	sumi += int(a) - int(b)
	if sumi < 0:
		sumi = 0
		j = i + 1
print(j)


N = int(input())
sumi = 0
j = 0
for i in range(N):
	(a, b) = input().split()
	sumi += int(a) - int(b)
	if sumi < 0:
		sumi = 0
		j = i + 1
print(j)


N = int(input())
summ = 0
res = 0
for n in range(N):
	(a, b) = map(int, input().split())
	summ += a - b
	if summ < 0:
		summ = 0
		res = n + 1
print(res)


N = int(input())
sumi = 0
maxi = 0
j = 0
for i in range(N):
	(a, b) = input().split()
	sumi += int(a) - int(b)
	if sumi < 0:
		sumi = 0
		j = i + 1
print(j)


n = int(input())
gas = 0
distance = 0
j = 0
for i in range(n):
	(a, b) = map(int, input().split())
	gas += a - b
	if gas < 0:
		gas = 0
		j = i + 1
print(j)


petrols = []
distances = []
n = int(input())
for i in range(n):
	(petrol, distance) = map(int, input().strip().split(' '))
	petrols.append(petrol)
	distances.append(distance)
start = 0
i = 0
total = 0
previous_total = 0
while i < n:
	while total >= 0 and i < n:
		total += petrols[i] - distances[i]
		i += 1
	previous_total = 0
	while total + previous_total < 0:
		previous_total += distances[start] - petrols[start]
		start += 1
	total += previous_total
print(start)


n = int(input())
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
for i in range(n):
	fuel = a[i][0] - a[i][1]
	for j in range(1, n):
		if fuel < 0:
			break
		station = (i + j) % n
		fuel = fuel + a[station][0] - a[station][1]
	if fuel >= 0:
		print(i)
		break


N = int(input())
sumi = 0
maxi = 0
j = 0
for i in range(N):
	(a, b) = input().split()
	sumi += int(a) - int(b)
	if sumi < 0:
		sumi = 0
		j = i + 1
print(j)


class Pump(object):

	def __init__(self, petrol, distance):
		self.petrol = petrol
		self.distance = distance

def can_finish_tour(pumps, start_index):
	start_pump = pumps[start_index]
	curr_petrol = start_pump.petrol
	distance_to_next_pump = start_pump.distance
	next_index = start_index + 1
	while next_index != start_index:
		if next_index == len(pumps):
			next_index = 0
		if curr_petrol < distance_to_next_pump:
			return False
		else:
			curr_petrol -= distance_to_next_pump
			next_pump = pumps[next_index]
			curr_petrol += next_pump.petrol
			distance_to_next_pump = next_pump.distance
			next_index += 1
	return True

def find_start(pumps):
	start_index = 0
	start_found = False
	while start_index < len(pumps) and (not start_found):
		start_found = can_finish_tour(pumps, start_index)
		if not start_found:
			start_index += 1
	return start_index
num_pumps = int(input().strip())
pumps = []
for i in range(num_pumps):
	stats = [int(j) for j in input().strip().split(' ')]
	pump = Pump(stats[0], stats[1])
	pumps.append(pump)
print(find_start(pumps))


class Solution:

	def __init__(self, stations):
		self.stations = stations

	def solve_case(self):
		start = 0
		while True:
			stations_passed = self.attempt(start)
			if stations_passed == len(self.stations):
				return start
			start += stations_passed + 1

	def attempt(self, start):
		petrol = 0
		destination = start
		stations_passed = -1
		distance_to_cover = 0
		while stations_passed < len(self.stations):
			petrol -= distance_to_cover
			if petrol < 0:
				break
			cur_station = self.stations[destination]
			petrol += cur_station[0]
			stations_passed += 1
			distance_to_cover = cur_station[1]
			destination = (destination + 1) % len(self.stations)
		return stations_passed
n = int(input())
stations = []
for i in range(n):
	(petrol, distance) = [int(_) for _ in input().split(' ')]
	stations.append((petrol, distance))
sln = Solution(stations)
print(sln.solve_case())


def travel(station, src, petrol, n):
	memoize = set()
	queue = []
	queue.append((src, 0))
	while len(queue):
		(current_station, remaining_petrol) = queue.pop(0)
		total_petrol = station[current_station][0] + remaining_petrol
		if current_station in memoize:
			return src
		if total_petrol >= station[current_station][1]:
			memoize.add(current_station)
			queue.append(((current_station + 1) % n, total_petrol - station[current_station][1]))
		else:
			return current_station + 1
n = int(input())
station = []
for i in range(n):
	k = [int(a) for a in input().split(' ')]
	station.append(k)
src = 0
while True:
	destination = travel(station, src, 0, n)
	if destination == src:
		print(src)
		break
	src = destination


def find_pump(pumps):
	for i in range(len(pumps)):
		gas = pumps[i]
		j = i + 1
		while j != i and gas >= 0:
			gas += pumps[j]
			j = (j + 1) % len(pumps)
		if i == j:
			return i
n = int(input())
pumps = []
for i in range(n):
	(give, take) = list(map(int, input().strip().split(' ')))
	pumps.append(give - take)
print(find_pump(pumps))


n = int(input())
m = [tuple((int(v) for v in input().split())) for i in range(n)]
total = sum((v[1] for v in m))
curdiff = 0
curindex = 0
for i in range(n):
	curdiff += m[i][0] - m[i][1]
	if curdiff < 0:
		curdiff = 0
		curindex = i + 1
print(curindex)


n = int(input().strip())
q = []
for n_i in range(n):
	q.append([int(x) for x in input().strip().split(' ')])
start_idx = 0
while start_idx < n:
	pump = q[0]
	petrol = pump[0]
	dist = pump[1]
	if dist > petrol:
		start_idx += 1
		q.append(q.pop(0))
	else:
		ttl_petrol = 0
		for i in range(n):
			pump = q[0]
			petrol = pump[0]
			dist = pump[1]
			ttl_petrol += petrol - dist
			q.append(q.pop(0))
			if ttl_petrol < 0:
				start_idx += i + 1
				break
		if ttl_petrol >= 0:
			break
print(start_idx)


def tour2(in_list):
	j = 0
	gu = 0
	for i in range(len(in_list)):
		cur_tup = in_list[i]
		gu += cur_tup[0] - cur_tup[1]
		if gu < 0:
			gu = 0
			j = i + 1
	return j
n = int(input().strip())
in_list = []
for i in range(n):
	in_list.append([int(j) for j in input().strip().split(' ')])
print(tour2(in_list))


N = int(input())
ans = 0
gas = 0
for i in range(N):
	(a, b) = [int(num) for num in input().split(' ')]
	gas = gas + (a - b)
	if gas < 0:
		gas = 0
		ans = i + 1
print(ans)


def canCompleteCircuit(gas, cost):
	if gas == None or cost == None:
		return -1
	total = 0
	upToNow = 0
	startPos = 0
	i = 0
	for i in range(len(gas)):
		delta = gas[i] - cost[i]
		if upToNow >= 0:
			upToNow = upToNow + delta
		else:
			upToNow = delta
			startPos = i
		total = total + delta
	return startPos

def main():
	N = int(input())
	gas = [None] * N
	cost = [None] * N
	for i in range(N):
		(gas[i], cost[i]) = map(int, input().split())
	print(canCompleteCircuit(gas, cost))
main()


from collections import deque
IDX = 0
PETROL = 1
KM_NEXT = 2

def can_complete(route):
	tank = 0
	for i in route:
		tank += i[PETROL] - i[KM_NEXT]
		if tank < 0:
			return False
	return True

def solve(T, inputs):
	q = deque()
	successes = []
	for i in inputs:
		q.append(i)
	for i in range(T):
		if can_complete(q):
			return q[0][0]
		q.rotate(-1)
	return -1
pumps = []
T = int(input())
for i in range(T):
	(p, km) = map(int, input().split())
	pumps.append((i, p, km))
print(solve(T, pumps))


n = int(input())
pumps = []
circle_size = 0
cum_sum = [0]
for _ in range(n):
	(fuel, distance) = [int(x) for x in input().strip().split()]
	cum_sum.append(cum_sum[-1] + fuel - distance)
print(min(enumerate(cum_sum[1:]), key=lambda a: a[1])[0] + 1)


import sys
n = int(input().strip())
arr = []
for arr_i in range(n):
	arr_t = [int(arr_temp) for arr_temp in input().strip().split(' ')]
	arr.append(arr_t)
start = 0
last = 0
l = 0
for pump in arr:
	l += pump[0]
	l -= pump[1]
	if l < 0:
		start = last + 1
		l = 0
	last += 1
print(start)


n = int(input().strip())
stations = [[int(s) for s in input().strip().split()] for i in range(n)]
start = g_delta = l_delta = 0
for i in range(n):
	l_delta = stations[i][0] - stations[i][1]
	if g_delta + l_delta < 0:
		if l_delta >= 0:
			start = i
			g_delta = l_delta
		else:
			start = i + 1
			g_delta = 0
	else:
		g_delta += l_delta
print(start)


def travel(station, src, petrol, n):
	memoize = set()
	queue = []
	queue.append((src, 0))
	while len(queue):
		(current_station, remaining_petrol) = queue.pop(0)
		total_petrol = station[current_station][0] + remaining_petrol
		if current_station in memoize:
			return src
		if total_petrol >= station[current_station][1]:
			memoize.add(current_station)
			queue.append(((current_station + 1) % n, total_petrol - station[current_station][1]))
		else:
			return current_station + 1
n = int(input())
station = []
for i in range(n):
	k = [int(a) for a in input().split(' ')]
	station.append(k)
src = 0
while True:
	destination = travel(station, src, 0, n)
	if destination == src:
		print(src)
		break
	src = destination


import sys

def readInt():
	return int(sys.stdin.readline())

def readInts():
	return [int(x) for x in sys.stdin.readline().split(' ')]
stations = readInt()
minGas = 9999999999
minStation = 9999999999
previousDistance = 0
currentGas = 0
for i in range(stations):
	values = readInts()
	stationGas = values[0]
	nextDistance = values[1]
	currentGas += stationGas
	currentGas -= nextDistance
	if currentGas < minGas:
		minGas = currentGas
		minStation = i
print(minStation + 1 % stations)


from collections import deque

def get_smallest_index(circle):
	cum_sum = []
	for (p, d) in reversed(circle):
		if not cum_sum:
			cum_sum.append(p - d)
		else:
			cum_sum.append(cum_sum[-1] + p - d)
	cum_sum = cum_sum[::-1]
	(curr_petrol, result_index) = (0, 0)
	for (i, (p, d)) in enumerate(circle):
		curr_petrol += p - d
		if curr_petrol < 0:
			if cum_sum[i] >= curr_petrol:
				result_index = i + 1
				curr_petrol = 0
	return result_index
n = int(input())
circle = deque()
for _ in range(n):
	(p, d) = [int(el) for el in input().split()]
	circle.append((p, d))
print(get_smallest_index(circle))


n = int(input())
gainChange = 0
m = (1, 0)
for i in range(n):
	info = input().split(' ')
	gainChange += int(info[0]) - int(info[1])
	if gainChange < m[1]:
		m = ((i + 1) % n, gainChange)
print(m[0])


class Loop(object):

	def __init__(self):
		self.length = int(input())
		self.distances = []
		self.amounts = []
		for station in range(0, self.length):
			(amount, distance) = map(int, input().strip().split())
			self.amounts.append(amount)
			self.distances.append(distance)

	def start_at(self, start=0, end=None):
		if end == None:
			end = self.length - 1
		for station in self.tour(start, end):
			next_station = (station + 1) % self.length
			prev_station = (station + self.length) % self.length
			if self.amounts[station] < self.distances[station]:
				return self.start_at(start=next_station, end=prev_station)
			else:
				self.amounts[next_station] += self.amounts[station] - self.distances[station]
		return start

	def tour(self, start, end):
		curr = start
		while curr != end:
			yield curr
			curr = (curr + 1) % self.length
		yield end
print(str(Loop().start_at()))


n = int(input())
q = []
for _ in range(n):
	(p, d) = list(map(int, input().split()))
	q.append(p - d)
i = 0
count = 0
p_sum = 0
while count < n:
	s = q.pop(0)
	p_sum += s
	if p_sum < 0:
		count = 0
		p_sum = 0
	else:
		count += 1
	q.append(s)
	i += 1
print(i % n)


from collections import deque
stations = int(input().strip())
circle = list()
for i in range(stations):
	current = input().strip().split(' ')
	circle.append((int(current[0]), int(current[1])))
visited = deque()
found = False
failed = False
starting_station = 0
station_index = 0
petrol = 0
traveled = 0
while not found and (not failed):
	if station_index - len(circle) is 0:
		station_index = 0
	current_station = circle[station_index]
	refill = current_station[0]
	next_distance = current_station[1]
	petrol -= traveled
	visited.append(-refill + next_distance)
	traveled = next_distance
	while petrol < 0:
		petrol += visited.popleft()
		starting_station += 1
	petrol += refill
	station_index += 1
	if len(visited) is 0:
		traveled = 0
		petrol = 0
	elif len(circle) - len(visited) <= 1:
		found = True
		solution = starting_station
	elif starting_station is stations:
		failed = True
		solution = -1
print(solution)


from queue import *

def whichPetrolPump(pumpQueue):
	amtPetrol = 0
	startPt = 0
	flag = True
	while 1:
		pump = pumpQueue.get()
		if startPt == pump[2] and (not flag):
			break
		flag = False
		if amtPetrol < 0:
			startPt = pump[2]
			amtPetrol = 0
		amtPetrol += pump[0]
		amtPetrol -= pump[1]
		pumpQueue.put(pump)
	return startPt

def main():
	N = int(input().strip())
	AllPetrolPumps = Queue()
	for i in range(N):
		petrolPump = [int(j) for j in input().strip().split(' ')] + [i]
		AllPetrolPumps.put(petrolPump)
	print(whichPetrolPump(AllPetrolPumps))
main()


n = int(input().strip())
stations = []
for i in range(n):
	station = [int(arr_temp) for arr_temp in input().strip().split(' ')]
	stations.append(station)
mini = float('inf')
pos = 0
total = 0
for i in range(n):
	total += stations[i][0] - stations[i][1]
	if total < mini:
		mini = total
		pos = i + 1
if pos == n:
	pos = 0
print(pos)


n = int(input())
pumps = []

def test(c, pumps):
	t = current[0] - current[1]
	for p in pumps:
		t = t + p[0] - p[1]
		if t < 0:
			return False
	return True
for __ in range(n):
	pumps.append([int(i) for i in input().split()])
possible = False
for i in range(n):
	current = pumps.pop(0)
	if current[0] >= current[1]:
		if test(current, pumps):
			print(i)
			possible = True
			break
	pumps.append(current)
if not possible:
	print(-1)


from collections import deque
circle = deque()
for _ in range(int(input())):
	circle.append([_] + list(map(int, input().split())))

def checkStation(q):
	gas = 0
	for stop in q:
		gas += stop[1]
		gas -= stop[2]
		if gas < 0:
			return False
	return True
while True:
	if checkStation(circle):
		print(circle[0][0])
		break
	else:
		circle.append(circle.popleft())


n = int(input())
li = []
sm = 0
for n0 in range(n):
	(a, b) = [int(i) for i in input().strip().split()]
	c = a - b
	li.append(c)
st = 0
for i in range(n):
	sm += li[i]
	if sm < 0:
		sm = 0
		st = i + 1
print(st)


N = int(input())
sumi = 0
maxi = 0
j = 0
for i in range(N):
	(a, b) = input().split()
	sumi += int(a) - int(b)
	if sumi < 0:
		sumi = 0
		j = i + 1
print(j)


import sys
n = int(sys.stdin.readline())
cum = [0]
min_cum = float('inf')
min_cum_idx = 0
for i in range(n):
	(p, d) = tuple([int(s) for s in sys.stdin.readline().split(' ')])
	cum.append(cum[-1] + p - d)
	if cum[-1] < min_cum:
		min_cum = cum[-1]
		min_cum_idx = i
print(min_cum_idx + 1)


N = int(input())
lst = [list(map(int, input().split())) for i in range(N)]
i = 0
count = 0
tmp = 0
fuel = 0
while count < N and tmp < N:
	if i == N:
		i = 0
	fuel += lst[i][0]
	fuel -= lst[i][1]
	i += 1
	count += 1
	if fuel < 0:
		fuel = 0
		count = 0
		tmp += 1
		i = tmp
print(tmp)


n = int(input())
x = [0] * (n + 1)
x[0] = 0
min_i = 0
min_v = 0
for i in range(1, n + 1):
	(a, b) = list(map(int, input().split(' ')))
	x[i] = x[i - 1] + a - b
	if min_v > x[i]:
		min_v = x[i]
		min_i = i
print(min_i)


class Stop:

	def __init__(self, gas, dist):
		self.gas = gas
		self.dist = dist
		self.adjusted_dist = 0

def test_loop(loop):
	carry = 0
	for stop in loop:
		if stop.gas - stop.dist + carry < 0:
			return False
		carry += stop.gas - stop.dist
	return True

def find_stop_index():
	stops = []
	N = int(input())
	for _ in range(N):
		stops.append(Stop(*[int(x) for x in input().split()]))
	for i in range(N):
		if test_loop(stops):
			return i
		stops.append(stops.pop(0))
	return -1
print(find_stop_index())


N = int(input().strip())
petrolAndDistance = []
for _ in range(N):
	petrolAndDistance.append(tuple((int(x) for x in input().strip().split())))

def checkIndex(idx):
	entry = petrolAndDistance[idx]
	runningPetrol = entry[0]
	runningDistance = entry[1]
	if runningPetrol < runningDistance:
		return False
	i = (idx + 1) % N
	while i != idx:
		currEntry = petrolAndDistance[i]
		runningPetrol += currEntry[0]
		runningDistance += currEntry[1]
		if runningPetrol < runningDistance:
			return False
		i = (i + 1) % N
	return True
idx = 0
while not checkIndex(idx):
	idx += 1
print(idx)


n = int(input())
a = 0
j = 0
suma = 0
for i in range(n):
	(x, y) = input().split(' ')
	(x, y) = (int(x), int(y))
	a = x - y
	suma += a
	if suma < 0:
		suma = 0
		j = i + 1
print(j)


N = int(input())
pumps = []
for n in range(N):
	(a, b) = map(int, input().split())
	pumps.append((a, b))
for i in range(N):
	total = 0
	for j in range(N):
		(a, b) = pumps[(i + j) % N]
		total += a - b
		if total < 0:
			break
	if total >= 0:
		print(i)
		break


n = int(input())
mindex = 0
gascount = 0
for a in range(n):
	(gas, distance) = input().split()
	(gas, distance) = (int(gas), int(distance))
	gascount += gas - distance
	if gascount < 0:
		gascount = 0
		mindex = a + 1
print(mindex)


n = int(input())
sums = 0
cand = 0
for i in range(n):
	(gas, distance) = list(map(int, input().split()))
	sums += gas - distance
	if sums < 0:
		cand = i + 1
		sums = 0
print(cand)


from functools import reduce
n = int(input())
print(reduce(lambda x, y: (y[0] if x[1] + y[1] < x[2] else x[0], x[1] + y[1], min(x[1] + y[1], x[2])), [(1, 0, 0)] + [(i + 1, reduce(lambda x, y: int(x) - int(y), input().split(' ')), 0) for i in range(n)])[0] % n)