Problem 1509. -- 做加法求和

1509: 做加法求和

Time Limit: 5 Sec  Memory Limit: 65535 MB   64bit IO Format: %lld
Submitted: 496  Accepted: 77
[Submit][Status][Web Board]

Description

给你一个正整数的集合,需要你每次从集合中选取2个数做加法,然后将选取的整数从集合中删除,再把他们的和添加到整数集合中。一直做到集合中只剩下一个整数就完成任务。
你的任务就是需要找出每次加法和的和的最小值是多少?

Input

有多组测试数据,每组测试数据占2行,第一行包含一个整数N(2≤N≤5000)。第2行给出N个正整数(≤100000)。

Output

每组测试数据的输出占一行,包含一个整数,表示集合中最后一个整数的最小值。

Sample Input

3
1 2 3
4
1 2 3 4

Sample Output

9
19

HINT

 sample input 1: 1 2 3


加法序列1:  1+2=3  3+3=6  和为3+6=9


加法序列2:  1+3=4  2+4=6  和为4+6=10


加法序列3:  2+3=5  1+5=6  和为5+6=11


和最小值为9



Source

[Submit][Status][Web Board]