Problem
英俊的杰克想建立自己的镒矿加工厂。
杰克控制着 n 家工厂，每家工厂都编号为 1 到 n。每一种植物都位于镒矿矿床，在那里也被联合开采。而且出厂编号越高，越新。
每个工厂都有其效率指数 a
i。它可以是正数、负数或零。
每个工厂都必须加工镒矿。您可以使用自己的矿床或通过管道获取过去由另一家工厂加工的矿石。然而，这个过程有些受限。首先，为了不使管道系统超载，每个工厂都可以严格地从彼此接受矿石进行进一步加工（或者不接受和使用自己的矿床）。其次，老工厂在技术上没有能力在新工厂之后再加工矿石。
整个系统的最终性能计算如下：对于每个工厂，其效率 a
i 乘以处理阶段，计算为进料矿石被处理的次数（有关更多详细信息，请参阅示例的解释），然后汇总所有植物的所有获得的值。
帮助Handsome Jack组织系统，使整个系统的整体性能尽可能的高。
输入：
第一行包含一个自然数 n (1 <= n <= 7) - 工厂的数量。
第二行包含 n 个以空格分隔的整数，其中第 i 个数字是 a
i (-1000 <= a
i <= 1000) - 基础效率编号为 i 的工厂。
输出：
打印单个数字——整个系统的最大可能总性能。
示例：
<正文>
| 输入 |
输出 |
3
1 5 3
| 20 |
3
1 5 -3 |
8 |
说明：
在第一个例子中，第一家工厂开采自己的矿石、第二家工厂从第一家工厂接收矿石、第三家从第二家工厂接收矿石是最有利可图的。在这种情况下，第一个工厂进行初级加工，其生产率是 1 * 1 = 1。第二个工厂进行二次加工，其生产率是 5 * 2 = 10。第三个工厂对接收到的矿石进行第三次加工，因此它的生产力是 3 * 3 = 9。总绩效是 1 + 10 + 9 = 20。
请注意，在这个例子中，第二个和第三个植物不能交换，因为由于技术原因，第二家工厂将无法在第三家工厂之后加工矿石，因为它比第三家老。
在第二个例子中，第一和第三工厂将使用他们的存款，第二工厂将从第一工厂接收矿石。