Emuskald is a well-known illusionist. One of his trademark tricks involves a set of magical boxes. The essence of the trick is in packing the boxes inside other boxes.

From the top view each magical box looks like a square with side length equal to 2^{k} (k is an integer, k ≥ 0) units. A magical box v can be put inside a magical box u, if side length of v is strictly less than the side length of u. In particular, Emuskald can put 4 boxes of side length 2^{k} - 1 into one box of side length 2^{k}, or as in the following figure:

 [Image] 

Emuskald is about to go on tour performing around the world, and needs to pack his magical boxes for the trip. He has decided that the best way to pack them would be inside another magical box, but magical boxes are quite expensive to make. Help him find the smallest magical box that can fit all his boxes.


-----Input-----

The first line of input contains an integer n (1 ≤ n ≤ 10^5), the number of different sizes of boxes Emuskald has. Each of following n lines contains two integers k_{i} and a_{i} (0 ≤ k_{i} ≤ 10^9, 1 ≤ a_{i} ≤ 10^9), which means that Emuskald has a_{i} boxes with side length 2^{k}_{i}. It is guaranteed that all of k_{i} are distinct.


-----Output-----

Output a single integer p, such that the smallest magical box that can contain all of Emuskald’s boxes has side length 2^{p}.


-----Examples-----
Input
2
0 3
1 5

Output
3

Input
1
0 4

Output
1

Input
2
1 10
2 2

Output
3



-----Note-----

Picture explanation. If we have 3 boxes with side length 2 and 5 boxes with side length 1, then we can put all these boxes inside a box with side length 4, for example, as shown in the picture.

In the second test case, we can put all four small boxes into a box with side length 2.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Mathematics

Greedy algorithms


Solutions:
from math import *
c = -1
for i in range(int(input())):
	(k, a) = list(map(int, input().split()))
	b = int(log(a, 4))
	if a != 4 ** b:
		b += 1
	if a == 1:
		b = 1
	c = max(c, k + b)
print(c)


import math
t = int(input())
ans = -1
maxi = -1
for i in range(t):
	(k, a) = list(map(int, input().split()))
	h = k + math.ceil(math.log(a, 4))
	ans = max(ans, h)
	maxi = max(maxi, k)
print(max(ans, maxi + 1))


from math import ceil, log
max_size = -1
for _ in range(int(input().strip())):
	(size, count) = map(int, input().strip().split())
	container = ceil(log(count, 4))
	max_size = max(max_size, size + max(container, 1))
print(max_size)


from math import *
n = int(input())
mx = 0
for i in range(n):
	(k, a) = map(int, input().split())
	mx = max(mx, 2 * k + log2(a))
	mx = max(mx, 2 * (k + 1))
print(int(ceil(mx / 2)))


import math
(n, o) = (int(input()), 0)
for i in range(n):
	(r, t) = map(int, input().split())
	r += math.ceil(math.log(t, 4))
	r += t == 1
	o = max(o, r)
print(o)


def main():
	n = int(input())
	m = b = 0
	for (k, a) in sorted((tuple(map(int, input().split())) for _ in range(n))):
		if k - m > 15:
			b = 1 if b else 0
		else:
			r = 4 ** (k - m)
			b = (b + r - 1) // r
		if b < a:
			b = a
		m = k
	if b == 1:
		k += 1
	else:
		r = 1
		while r < b:
			r *= 4
			k += 1
	print(k)

def __starting_point():
	main()
__starting_point()


import sys
input = sys.stdin.readline
n = int(input())
ka = [list(map(int, input().split())) for i in range(n)]
m = 0
max_k = 0
for (k, a) in ka:
	max_k = max(k, max_k)
	cnt = k
	x = 1
	while x < a:
		x *= 4
		cnt += 1
	m = max(m, cnt)
if max_k == m:
	m += 1
print(max(m, 1))


n = int(input())
qq = 0
for i in range(n):
	(h, m) = list(map(int, input().split()))
	k = 1
	r = 4
	while m > r:
		k += 1
		r *= 4
	qq = max(qq, h + k)
print(qq)


n = int(input())
t = [tuple(map(int, input().split())) for i in range(n)]
m = max(t)
d = 2 * m[0] + len(bin(m[1])) - 1
t = sorted([i for i in t if 2 * i[0] + len(bin(i[1])) > d])
(p, k) = (t[0][0], t[0][1] - 1)
for i in range(1, len(t)):
	(p, k) = (t[i][0], max(t[i][1] - 1, k >> 2 * (t[i][0] - p)))
print(p + (len(bin(k)) + 1) // 2 - 1)


import math as m
r = 0
for _ in range(int(input())):
	(k, a) = [int(x) for x in input().split()]
	e = 0
	v = 1
	while v < a:
		v *= 4
		e += 1
	if e + k > r:
		r = e + k
	if k + 1 > r:
		r = k + 1
print(r)


from sys import stdin
input = stdin.readline
n = int(input())
res = 0
for i in range(n):
	(k, a) = (int(x) for x in input().split())
	if k == 0:
		res = max(res, 1)
	i = 1
	x = 4
	while a > x:
		i += 1
		x *= 4
	res = max(res, k + i)
print(res)


import copy
import itertools
import string
import sys

def powmod(x, p, m):
	if p <= 0:
		return 1
	if p <= 1:
		return x % m
	return powmod(x * x % m, p // 2, m) * (x % m) ** (p % 2) % m

def to_basex(num, x):
	while num > 0:
		yield (num % x)
		num //= x

def from_basex(it, x):
	ret = 0
	p = 1
	for d in it:
		ret += d * p
		p *= x
	return ret

def l4(x):
	ret = 1
	while x > 4:
		ret += 1
		x += 3
		x //= 4
	return ret

def core():
	n = int(input())
	ans = 0
	for _ in range(n):
		(k, a) = (int(x) for x in input().split())
		ans = max(ans, l4(a) + k)
	print(ans)
core()