Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

A. Magical Boxes

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputEmuskald 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:

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^{ki}. 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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/15/2018 11:09:28 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|