Девочка Лена — самая экономная девочка в Москве. Поэтому когда папа поручил ей закупку продуктов для поездки на дачу, она сразу отправилась в самый лучший магазин — «PriceFixed». У этого магазина есть несколько особенностей:
- В магазине есть бесконечный запас каждого товара.
- Все товары в нем стоят одинаково — ровно \(2\) рубля за единицу товара.
- Для каждого из \(i\) товаров предусмотрена скидка для опытных покупателей: если вы уже приобрели \(b_i\) единиц товаров (любого типа, не обязательно типа \(i\)), то на все последующие покупки \(i\)-го товара будет действовать скидка \(50\%\) (то есть единицу \(i\)-го товара можно будет купить за \(1\) рубль!).
Лене нужно купить \(n\) товаров: \(i\)-го товара нужно купить не менее \(a_i\) единиц. Помогите Лене понять, какую минимальную сумму денег ей нужно будет потратить, если она будет выбирать порядок покупки товаров оптимальным образом. Обратите внимание, Лена, если хочет, может купить больше единиц некоторого товара, чем необходимо.
Выходные данные
Выведите искомую минимальную сумму, которая требуется Лене для совершения всех покупок.
Примечание
В первом примере из условия Лена может купить товары в таком порядке:
- единицу товара \(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
|