Девочка Лена — самая экономная девочка в Москве. Поэтому когда папа поручил ей закупку продуктов для поездки на дачу, она сразу отправилась в самый лучший магазин — <<PriceFixed>>. У этого магазина есть несколько особенностей:
-
В магазине есть бесконечный запас каждого товара.
-
Все товары в нем стоят одинаково — ровно 2 рубля.
-
Для каждого из \(i\) товаров предусмотрена скидка для опытных покупателей: если вы уже приобрели \(b_i\) товаров (любого типа, не обязательно типа \(i\)), то на все последующие покупки \(i\)-го товара будет действовать скидка \(50\%\) (то есть, \(i\)-й товар можно будет покупать за 1 рубль!).
Лене нужно купить \(n\) товаров: \(i\)-го товара нужно купить \(a_i\) штук. Помогите Лене понять, какую минимальную сумму денег ей нужно будет потратить, если она будет выбирать порядок покупки товаров оптимальным образом.
Формат входных данных
В первой строке вводится число \(n\) \((1 \leq n \leq 100\,000)\) — количество различных товаров в списке.
В следующих \(n\) строках вводятся описания товаров. Каждое описание состоит из двух чисел \(a_i\) и \(b_i\), (\(1 \leq a_i \leq 10^{14}\), \(1 \leq b_i \leq 10^{14}\)) — требуемое число товаров типа \(i\) и сколько товаров нужно купить, чтобы получить скидку на товар \(i\).
Сумма всех \(a_i\) в тесте не превосходит \(10^{14}\).
Формат выходных данных
Выведите искомую минимальную сумму, которая требуется Лене для совершения всех покупок.
Примечание
В первом примере из условия Лена может купить товары в таком порядке:
-
единицу товара 3 за 2 рубля,
-
единицу товара 1 за 2 рубля
-
единицу товара 1 за 2 рубля,
-
единицу товара 2 за 1 рубль (она может купить его со скидкой, так как уже куплено 3 товара),
-
единицу товара 1 за 1 рубль (она может купить его со скидкой, так как уже куплено 4 товара).
Суммарно она потратит 8 рублей. Можно показать, что меньше потратить невозможно.
Во втором примере из условия Лена может купить товары в таком порядке:
-
единицу товара 1 за 2 рубля,
-
две единицы товара 2 по 2 рубля за каждую,
-
единицу товара 5 за 2 рубля,
-
единицу товара 3 за 1 рубль,
-
две единицы товара 4 по 1 рублю за каждую,
-
единицу товара 1 за 1 рубль.
Суммарно при таком порядке приобретения товаров Лена потратит 12 рублей.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 4
1 3
1 5
|
8
|
|
2
|
5
2 7
2 8
1 2
2 4
1 8
|
12
|