甄总搬石头
题号:NC14407
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 32 M,其他语言64 M
64bit IO Format: %lld

题目描述

现在草地上有n堆石头,甄总想要合并这n堆石头成为1堆,但是他每次能力有限,所以只能一次合并2堆石头至1堆。
现在已知第i堆石头有ai块,假设甄总要合并第i堆和第j堆石头,则需要花费ai+aj的力气。
给出n堆石头每堆石头的个数,求出甄总要合并n堆成1堆石头一共需要多少力气。

输入描述:

第1行输入一个整数n,代表一共有n堆石头。
第2行输入n个整数ai,表示第i堆有ai块石头。

输出描述:

输出一行整数,表示一共需要多少力气。
示例1

输入

复制
3
1 2 3

输出

复制
9