小钻石合并【动态规划 DP专题训练】 1270

在这个风和日丽，寒风吹彻的大年夜里，我们迎来了情人节。要知道，情人节是一个很重要的节日哦~(*^__^*) 嘻嘻……尤其是对于某些人面兽心的老师来说。 但是众所周知，老师为了付房贷，把身上的钱都用完了。那样就没有钱给MM买情人节礼物了？老师很伤心。。。╮(╯_╰)╭露出了自己险恶的埋藏在人皮下的真面目，说要是我们不能想办法帮助老师弄到钱，他就惩罚全小组同学听他和冯迭乔大神牛一起唱《Just beat it》。 ~~~~(>_<)~~~~ 大家都一下子慌张了起来。 然而，我们宇宙超级无敌霹雳可爱的年仅1岁的组长，拿出了藏在家里地下室里的《教主宝典》，翻到了神奇的第*****页，用那无比可爱的语气，给大家读。 为了欢迎农历新年，清牛在镇中的操场的四周摆放N堆钻石,现要将钻石有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的钻石数，记为该次合并所得到的奖金。 为了让老师能够尽可能多拿到奖金，好去送给MM们，看题的各位神牛们决定写程序帮助老师。 可是组长又说，老师太坏了，肯定还是会唱歌的，所以我们也要算出最小收益，如果老师没请我们吃饭，就让他拿到最小收益。(*^__^*) 当然最后的结果肯定是李老师又赖皮了，所以我们只需要输出最小收益即可。。。。

数据的第1行试正整数N,1≤N≤1000,表示有N堆钻石.第2行有N个数,分别表示每堆钻石的个数.

输出共1行为最小收益