Максим всегда ходит в супермаркет по воскресеньям. Сегодня в супермаркете действует система скидок.
Существует m видов скидок. Будем считать, что скидки пронумерованы от 1 до m. Чтобы воспользоваться скидкой номер i, покупатель берет специальную корзину, в которую кладет ровно qi товаров, которые он покупает. По условиям акции, в дополнение к положенным в корзину товарам покупатель может получить не более двух товаров из супермаркета бесплатно. Выбор количества «бесплатных товаров» (0, 1 или 2) и самих товаров предоставляется покупателю. Единственное условие, которое накладывается на выбранные «бесплатные товары»: каждый из них должен быть не дороже самого дешевого товара из qi товаров корзины.
Сейчас Максиму нужно купить n товаров в магазине. Посчитайте, за какую минимальную сумму денег Максим сможет их купить, если он будет пользоваться системой скидок максимально оптимально.
Считайте, что в супермаркете имеется достаточное количество корзин для любых действий. Одну и туже скидку разрешается использовать несколько раз. Конечно, Максим может покупать товары без использования каких-либо скидок.
Выходные данные
В единственную строку выведите целое число — ответ на задачу.
Примечание
В первом примере Максиму нужно купить два товара стоимостью 100 и получить по скидке два товара стоимостью 50 бесплатно. В таком случае Максим заплатит 200.
Во втором примере Максиму выгодно купить 3 товара, а 2 получить бесплатно по скидке. В таком случае Максим заплатит 150.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
2
4
50 50 100 100
|
200
|
|
2
|
2
2 3
5
50 50 50 50 50
|
150
|
|
3
|
1
1
7
1 1 1 1 1 1 1
|
3
|