外星微生物

题目描述

在仙女座某星系中发现一种微生物，这种生物可以在条件合适的情况下进行合并，每次合并时只能两个生物合并成一个生物，合并后体重为两个生物的体重总和，目前小童已经研制出可以使这种生物合并的药剂，当给相邻的两个生物分别使用这种药剂，它们就可以合成一个新的生物。药剂的用量与每个生物的体重成正比，如：a 生物体重为 5，b 生物体重为 6，它们在合并时需要消耗 11 的药剂量。现在有一排生物，已知每个生物的体重，它们的位置关系无法改变，怎么样才能在最节省药剂的情况下，使它们变成一个生物。

输入格式

输入一个整数 $n$，表示一排生物的数量。

接下来 $n$ 行，每行一个正整数，小于 $10000$，分别表示第 $i$ 个生物的体重（$1 \le i \le n$）。

输出格式

输出最小消耗的药剂量。

样例输入 #1

3
2
3
5

样例输出 #1

15

数据范围

$2 \le n \le 100$

每个生物的体重为小于 $10000$ 的正整数。

知识点与难度

本题涉及的知识点从属于 GESP七级（区间DP、动态规划），难度等级：Mid+。

测试点分布