题目描述

在一个果园里，多多已经将所有的果子堆成了若干堆。

现在需要将所有果子合并成一堆。每次只能合并两堆果子，合并的消耗体力等于两堆果子的数量之和。

请你求出将所有果子合并为一堆，需要花费的最小体力总和。

输入格式

共两行，第一行包含一个整数 $n$，表示果子的堆数。

第二行有 $n$ 个正整数，每两个正整数之间用一个空格隔开，表示每堆果子的数量。

输出格式

一个整数，表示合并所有果子需要的最小体力。

输入输出样例

【输入样例 1】

4
1 2 9 7

【输出样例 1】

30

数据说明

对于 $100\%$ 的数据，$2 \leq n \leq 1000$，每堆果子数量不超过 $1000$。