Codeforces Round 165 (Div. 1) |
---|
Закончено |
Эмускальд — известный иллюзионист. Для своего коронного номера он использует набор волшебных ларцов. Суть фокуса — в том, чтобы поместить ларцы внутрь других ларцов.
Сверху каждый волшебный ларец выглядит как квадрат со стороной равной 2k (k — целое, k ≥ 0) единиц. Ларец v можно положить в ларец u, если длина стороны ларца v строго меньше, чем длина стороны ларца u. В частности, Эмускальд может положить 4 ларца со сторонами 2k - 1 в один ларец со стороной 2k. Вид вложенных друг в друга ларцов показан на следующем рисунке:
Эмускальд собирается в мировое турне. Ему надо упаковать свои волшебные ларцы для путешествия. Он решил, что лучше всего будет уложить их все в другой ларец, но мастерить волшебные ларцы достаточно дорого. Помогите ему найти наименьший волшебный ларец, в который можно поместить все его ларцы.
Первая строка входных данных содержит целое число n (1 ≤ n ≤ 105), количество различных размеров ларцов в распоряжении Эмускальда. В следующих n строках записано по два целых числа ki и ai (0 ≤ ki ≤ 109, 1 ≤ ai ≤ 109), что означает, что у Эмускальда есть ai ларцов со стороной 2ki. Гарантируется, что все ki различны.
Выведите единственное целое число p, такое что длина стороны наименьшего ларца, который может вместить в себя все ларцы Эмускальда, равна 2p.
2
0 3
1 5
3
1
0 4
1
2
1 10
2 2
3
Пояснение рисунка. Если у нас есть 3 ларца со стороной 2 и 5 ларцов со стороной 1, то мы можем уместить их все в ларце со стороной 4, например, так, как показано на рисунке.
Во втором примере мы можем уложить все четыре маленьких ларца в ларец со стороной 2.
Название |
---|