← 返回题目列表

Codeforces · 269/A

A. 魔法盒

中文机器翻译题面 查看原题

Emuskald 是一位著名的魔术师。他的标志性技巧之一涉及一组神奇的盒子。这个技巧的本质是将盒子装进其他盒子里。

从俯视图看,每个魔法盒看起来都是一个边长等于 2k(k 为整数,k ≥ 0)个单位的正方形。如果 v 的边长严格小于 u 的边长,则可以将魔盒 v 放入魔盒 u 内。具体来说,Emuskald可以将4个边长为2k - 1的盒子放入1个边长为2k的盒子中,或者如下图:

Emuskald 即将前往世界各地巡演,他需要为这次旅行收拾好他的魔法盒子。他决定将它们包装在另一个神奇的盒子里,但神奇的盒子制造起来相当昂贵。帮助他找到能装下他所有盒子的最小魔法盒子。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 105),即 Emuskald 拥有的不同大小的盒子的数量。接下来的 n 行每行包含两个整数 ki 和 ai (0 ≤ ki ≤ 109, 1 ≤ ai ≤ 109),这意味着 Emuskald 有边长为 2ki 的 ai 框。保证所有的 ki 都是不同的。

输出

输出单个整数 p,使得可以包含所有 Emuskald 盒子的最小魔法盒子的边长为 2p。

示例

输入 #1

2
0 3
1 5

输出 #1

3

输入 #2

1
0 4

输出 #2

1

输入 #3

2
1 10
2 2

输出 #3

3

注意

图片说明。如果我们有 3 个边长为 2 的盒子和 5 个边长为 1 的盒子,那么我们可以将所有这些盒子放在一个边长为 4 的盒子中,例如如图所示。

在第二个测试用例中,我们可以将所有四个小盒子放入一个边长为2的盒子中。