Description

李华现在接到一个任务，他需要帮建筑公司将n堆石头合并到一堆，让李华苦恼的是，搬运石头非常费力，每次合并只能合并两堆石头，消耗的体力为两堆石头的重量之和。现在李华来请教你，希望你能给出将这n堆石头合并成一堆石头所消耗体力的最小值。

Input Format

输入包含两行整数

第一行是一个整数n，表示有几堆石头。

第二行给出n个整数，第i个数ai表示第i堆石头重量

1≤n≤10000

1≤ai≤20000

Output Format

输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。

输入数据保证这个值小于 2^31

3 
1 2 9​

15