该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目

在乐队练习的准备期间，高松灯因为是全职主唱，没什么可准备的，想帮忙却又被立希坚定的拒绝了。于是在一旁无聊地玩起了纸条，她把纸条整齐地分成了n段，每段的长度分别为$a_1$，$a_2$，……，$a_n$，然后她又把纸条恢复成原样，她先把两段纸条用胶水接在一起，使之变成一段纸条，然后重复此步骤，直到最后变成只剩一段纸条。高松灯不断地思考着到底有多少种不同的组合方式，沉浸在自己的世界中。已经准备好的立希看到了在认真思考的灯，便上前询问，得知事情的始末后，立希便陪着灯一起想了起来。在乐队练习开始前，灯对立希表达了感谢，立希面对着灯说“只要和灯在一起，即使思考一辈子的题也没关系”。在一旁的ano酱看到了这一幕，问到“那...那我呢？”，立希说“那你把每次都用到的纸条长度加在一起，告诉我最终得到的最小结果再说吧。”这可把ano酱难住了，但ano酱是不会放弃的。所以你能帮帮ano酱找出正确答案吗？

(立希终于在某个平行宇宙赢了一次。她真的，我哭死)

输入

第一行输入n (1$\leq$n$\leq$20000);

第二行输入$a_1$，$a_2$，……，$a_n$.(0$\leq$$a_i$$\leq$50000)

输出

最少的长度

样例

3
8 5 8

34

样例解释

拼接 5 和 8的纸条，此时用到的纸条长度为 13 ，然后再拼接13 和 8 的纸条，此时只剩一个纸条，结束拼接。所以最终答案为34。