logo AlgoBeat OnlineJudge
登录 注册

#200330. 瑞瑞的木板

内存限制:125 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

瑞瑞想要亲自修复在他的一个小牧场周围的围栏。


他测量栅栏并发现他需要 根木板,每根的长度为整数 。于是,他买了一根足够长的木板,长度为所需的 根木板的长度的总和,他决定将这根木板切成所需的 根木板(瑞瑞在切割木板时不会产生木屑,不需考虑切割时损耗的长度)。

瑞瑞切割木板时使用的是一种特殊的方式,这种方式在将一根长度为 的木板切为两根时,需要消耗 个单位的能量。瑞瑞拥有无尽的能量,但现在提倡节约能量,所以作为榜样,他决定尽可能节约能量。显然,总共需要切割 次,问题是,每次应该怎么切呢?请编程计算最少需要消耗的能量总和。

输入格式

输入的第一行是整数,表示所需木板的数量

到第 行,每行一个整数,第 行的整数 代表第 根木板的长度

输出格式

一个整数,表示最少需要消耗的能量总和。

样例

样例输入 1

3
8
5
8

样例输出 1

34

数据范围与提示

输入输出样例 1 解释

将长度为 的木板,第一次切割为长度为 和长度为 的,消耗 个单位的能量,第二次将长度为 的木板切割为长度为 的,消耗 个单位的能量,共消耗 个单位的能量,是消耗能量最小的方案。


数据规模与约定

  • 对于 的数据,保证