题目描述
YuMS的笔记本群要开始工作了,可是YuMS买的路由器巨垃圾,只能连出两条线,一条上面笔记本们串联,另一条上面笔记本们并联。这使他的笔记本只能像电路一样,笔记本与路由器不是星状排布,而是笔记本之间的线状连接。我们设想连接的时候串连的笔记本中每台笔记本们性能都将变为这条支路上性能最低的一台的性能;并联的几台笔记本中每台笔记本的性能变为他们性能的平均数除以2,并联路要求至少有两台笔记本;并联的电脑们性能不受串联路的影响,也就是说图一中Acer机与Hasee机相互制约,而与其他笔记本无关;并联的几台笔记本中每台笔记本的性能变为他们性能的平均数除以2,而与Acer、Hasee无关。为了使问题变得简单一些,我们规定类似电路的这个连接中
1. 并联不能与并联串连;(图二)
2. 并联中不能出现串连(图三、四)
即如图一所示,而不会出现如图二、三、四所示的连接方式。YuMS还打算把加上还不如不加的电脑留下玩游戏,即他不一定用掉所有的笔记本。
YuMS没有精力再去编这程序了,否则他会累的生病,现在请您帮她作出设计方案,只要求输出最终笔记本群性能总和的最大值。
输入格式
输入文件第1行有一个整数n,表示共买了n台笔记本电脑。从第2行开始,每行有一个整数代表笔记本的性能。
【范围说明】
对于30%的数据n<=5
对于100%的数据,n<=20
输出格式
输出文件只包含一个实数(保留两位小数),表示你设计的方案中笔记本群的性能总和最大值。
样例输入
样例输出