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

Девочка Лена — самая экономная девочка в Москве. Поэтому когда папа поручил ей закупку продуктов для поездки на дачу, она сразу отправилась в самый лучший магазин — «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}$$$.

Выходные данные

Выведите искомую минимальную сумму, которая требуется Лене для совершения всех покупок.

Система оценки

В данной задаче $$$20$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$5$$$ баллов. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.

Обозначим за $$$A$$$ сумму по всем $$$a_i$$$ в тесте.

Решения, корректно работающие при $$$n, A \le 8$$$, наберут не менее $$$20$$$ баллов.

Решения, корректно работающие при $$$n, A \le 15$$$, наберут не менее $$$40$$$ баллов.

Решения, корректно работающие при $$$n, A \le 1000$$$, наберут не менее $$$60$$$ баллов.

Решения, корректно работающие при $$$n, A \le 100\,000$$$, наберут не менее $$$80$$$ баллов.

Примеры
Входные данные
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 рублей.