|
Олимпиады прошлых лет
|
||||||||||||||||||||||||||||||
|
Олимпиада проводится при поддержке Компьютерного супермаркета "НИКС" и компании Genius
Информационная поддержка:
журнал "Мир ПК"
II Всероссийская заочная олимпиада школьников по информатике, 2007/08 учебный год
Задача C. Скидки
| Имя входного файла: | c.in |
| Имя выходного файла: | c.out |
| Максимальное время работы на одном тесте: | 1 секунда |
| Максимальный объем используемой памяти: | 64 мегабайта |
В супермаркете проводится беспрецедентная акция - "Покупая два любых товара, третий получаешь бесплатно*", а внизу мелким шрифтом приписано "* - из трех выбранных вами товаров оплачиваются два наиболее дорогих".
Вася, идя в супермаркет, определился, какие товары он хочет купить, и узнал, сколько они стоят. Помогите ему определить минимальную сумму денег, которую ему нужно взять с собой, чтобы в итоге стать счастливым обладателем этих товаров.
Формат входных данных
Во входном файле задано сначала число N (1≤N≤1000), а затем N чисел - стоимости выбранных Васей товаров. Все стоимости - натуральные числа, не превышающие 10000.
Формат выходных данных
В выходной файл выведите одно число - сумму денег, которую Вася должен взять с собой в супермаркет (минимально возможную).
Примеры
| c.in | c.out | Пояснение |
6 1 5 4 3 5 7 |
19 |
Вася сначала пройдет через кассу с товарами стоимостью 1, 3 и 4 - заплатит 7 рублей и товар стоимостью 1 получит в подарок, а затем снова зайдет в супермаркет и купит товары стоимостью 5 и 7, еще один товар стоимостью 5 получив в подарок. |
5 3 15 25 8 8 |
51 |
Вася в первый заход в супермаркет купит товары стоимостью 15 и 25 рублей, в качестве подарка взяв товар стоимостью 8 рублей. А во второй заход в супермаркет купит товары стоимостью 3 и 8, не взяв никакого подарка. |