D. PriceFixed
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Девочка Лена — самая экономная девочка в Москве. Поэтому когда папа поручил ей закупку продуктов для поездки на дачу, она сразу отправилась в самый лучший магазин — «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
3 4
1 3
1 5
Выходные данные
8
Входные данные
5
2 7
2 8
1 2
2 4
1 8
Выходные данные
12
Примечание

В первом примере из условия Лена может купить товары в таком порядке:

  1. единицу товара $$$3$$$ за $$$2$$$ рубля,
  2. единицу товара $$$1$$$ за $$$2$$$ рубля
  3. единицу товара $$$1$$$ за $$$2$$$ рубля,
  4. единицу товара $$$2$$$ за $$$1$$$ рубль (она может купить его со скидкой, так как уже куплено $$$3$$$ товара),
  5. единицу товара $$$1$$$ за $$$1$$$ рубль (она может купить его со скидкой, так как уже куплено $$$4$$$ товара).

Суммарно она потратит $$$8$$$ рублей. Можно показать, что меньше потратить невозможно.

Во втором примере из условия Лена может купить товары в таком порядке:

  1. единицу товара $$$1$$$ за $$$2$$$ рубля,
  2. две единицы товара $$$2$$$ по $$$2$$$ рубля за каждую,
  3. единицу товара $$$5$$$ за $$$2$$$ рубля,
  4. единицу товара $$$3$$$ за $$$1$$$ рубль,
  5. две единицы товара $$$4$$$ по $$$1$$$ рублю за каждую,
  6. единицу товара $$$1$$$ за $$$1$$$ рубль.

Суммарно при таком порядке приобретения товаров Лена потратит $$$12$$$ рублей.