题目描述

有$n$堆石子,重量分别为${w_i}$ ,现在想要把这些石子合并成一堆,每次可以选择最多任意$3$ 堆进行合并,代价为选择的所有石子的重量之和,问把所有的石子合成一堆最少需要多少代价?


输入格式

第一行包括一个正整数$n (1\leq n\leq 10^5)$表示有$n$堆石子
第二行包括$n$ 个正整数${w_i} ({w_i } \leq 10^9)$,表示石子的重量


输出格式

输出一个正整数 表示合并所有石子所需的最小代价


样例数据

输入

4
1 2 3 4

输出

13

备注


信息

时间限制: 1s
内存限制: 128MB
评测模式: Normal

导航

比赛介绍
比赛排名
数据统计
评测状态
答疑平台
打印服务