Задача №1099. Скидки
В супермаркете проводится беспрецедентная акция – «Покупая два любых товара, третий получаешь бесплатно*», а внизу мелким шрифтом приписано «* - из трех выбранных вами товаров оплачиваются два наиболее дорогих».
Вася, идя в супермаркет, определился, какие товары он хочет купить, и узнал, сколько они стоят. Помогите ему определить минимальную сумму денег, которую ему нужно взять с собой, чтобы в итоге стать счастливым обладателем этих товаров.
Во входном файле задано сначала число N (1≤N≤1000), а затем N чисел – стоимости выбранных Васей товаров. Все стоимости – натуральные числа, не превышающие 10000.
В выходной файл выведите одно число – сумму денег, которую Вася должен взять с собой в супермаркет (минимально возможную).
Комментарии к примерам тестов
1. Вася сначала пройдет через кассу с товарами стоимостью 1, 3 и 4 – заплатит 7 рублей и товар стоимостью 1 получит в подарок, а затем снова зайдет в супермаркет и купит товары стоимостью 5 и 7, еще один товар стоимостью 5 получив в подарок.
2. Вася в первый заход в супермаркет купит товары стоимостью 15 и 25 рублей, в качестве подарка взяв товар стоимостью 8 рублей. А во второй заход в супермаркет купит товары стоимостью 3 и 8, не взяв никакого подарка.
6 1 5 4 3 5 7
19
5 3 15 25 8 8
51