五一促销活动

题目描述

五一假期，超市促销活动：

有n件商品，第i件商品的价格是ai,晨晨想把这些商品全都买下。现在正处于五一促销活动期间，凡是购买两件商品，就可以免费带走第三件商品，只要免费商品的价格不超过付费商品中任意一个商品的价格即可。

请问，最少需要多少钱，才能把n件商品全都买回去？

输入描述

第一行：一个整数表示n；

第二行：n个整数表示a1​,a2​,…,an​。

输出描述

单个整数：表示将所有商品买下的最少钱数。

数据范围

• 对于40%的数据，1≤n≤100；
• 对于70%的数据，1≤n≤5000；
• 对于100%的数据，1≤n≤100,000，1≤ai​≤30,000。