题目描述

小泽有 $n$ 堆石子。每次选择两堆合并，消耗的体力等于两堆石子数之和，新堆石子数也为这个和。重复到只剩一堆，求最小总消耗。

输入格式

第一行整数 $n$，第二行 $n$ 个整数 $a_i$。

输出格式

输出最小总消耗。

输入

3
8059 18142 4476

输出

43212

输入

4
7462 14445 19302 451

输出

71931

输入

42
17879 11953 19186 2306 1729 6860 3512 5765 11303 439 12037 12898 16677 6406 16372 13628 4136 18619 15082 2200 8263 15295 11930 10909 4308 18973 18026 15718 18611 10115 4741 16310 19843 18050 11270 15508 18333 3652 7307 10681 846 16287

输出

2454490

数据范围

$1\le n\le10^4$，$1\le a_i\le2\times10^4$。