合并货物

题目描述

有 n 堆货物，每堆的重量为 a_i。每次选择两堆合并成一堆，花费为两堆重量之和。求合并为一堆所需的最小总花费。建议练习小根堆 priority_queue。

输入格式

第一行 n，第二行 n 个正整数。

输出格式

输出最小总花费。

数据范围

1≤n≤100000；1≤a_i≤10^6。

样例

3
347826 677739 638840

2651071

6
776416 648771 109639 819609 743441 736539

9907220

说明

所有题目均为标准输入、标准输出；不需要文件读写。函数专题的函数签名是教学要求，普通 OJ 仅能依据程序输出来评测。