2018 WUSTACM 新生交流群:829055498

Problem 1364. -- 挂灯笼

1364: 挂灯笼

Time Limit: 1 Sec  Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 49  Accepted: 7
[Submit][Status][Web Board]

Description

WUST校园内有一棵神奇的树(二叉树),即树的每一个节点只有两个分支。现在2015年元旦节马上要到了,学校需要派一个人将n个灯笼挂到这棵树上(灯笼只能挂到树的节点上),由于需要遵守某些习俗的原因,当树上的一个节点挂了灯笼后,由这个节点开始产生的所有的分支都不准挂灯笼。已知每个灯笼都有一个重量W,而每个灯笼挂到树上所消耗的体力是树的根节点(地面)到灯笼的位置之间的距离L+1W的乘积(两相邻节点之间距离为1)。由于这个人体力有限,所以希望花费的体力最少,你能帮他算算他花费的最少体力是多少吗?

Input

多组测试

每行首先有个n(0<=n<=10000)表示灯笼的数量,接下来一行每行有n个数表示灯笼的重量W(0<=W<=10000)

Output

对于每个测试输出一个整数表示花费的最少体力

Sample Input

4
1 1 2 1
1
1

Sample Output

15
1

Source

[Submit][Status][Web Board]