Задача №115124. PriceFixed
Участникам, использующим язык Python3 , рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3 .
Девочка Лена — самая экономная девочка в Москве. Поэтому когда папа поручил ей закупку продуктов для поездки на дачу, она сразу отправилась в самый лучший магазин — «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 рублей.
В данной задаче \(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