Codeforces Round 727 (Div. 2) |
---|
Закончено |
Девочка Лена — самая экономная девочка в Москве. Поэтому когда папа поручил ей закупку продуктов для поездки на дачу, она сразу отправилась в самый лучший магазин — «PriceFixed». У этого магазина есть несколько особенностей:
Лене нужно купить $$$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
В первом примере из условия Лена может купить товары в таком порядке:
Суммарно она потратит $$$8$$$ рублей. Можно показать, что меньше потратить невозможно.
Во втором примере из условия Лена может купить товары в таком порядке:
Суммарно при таком порядке приобретения товаров Лена потратит $$$12$$$ рублей.
Название |
---|