题目内容

深度学习算法由一个个计算单元组成，我们称这些计算单元为算子。

对于完成矢量运的算子我们称为矢量算子，在 $NPU$ 中矩阵计算单元和向量计算单元都可以执行矢量算子，他们是独立可并行执行的，但他们的计算效率是6:1，即假设某个失量算子在矩阵计算单元上执行的时间为 $N$ ，则在向量计算单元上执行的时间为 $6N$ 。

给定一组矢量算子，假设他们都可以部署在矩阵计算单元和向量计算单元。为了充分利用计算资源，我们可以合理部署算子的执行单元，让总体的执行时间最短，总的执行时间为 $MAX$ (矩阵计算单元总的执行时间，向量计算单元总的执行时间)。

为了简化计算模型，我们约定:

1.单个算子只能部署在矩阵计算单元或向量计算单元。

2.部署在向量计算单元的算子必须是按照给定顺序连续的。

输入描述

输入格式:

第一行输入算子数 $n$

第二行输入该组算子在矩阵计算单元的执行时间 $nums$

$1<=n<= 10^4$

$1 <=nums[i] <=10^4$

输出描述

该组算子整体的最短执行时间

样例1

输入

9
1 2 3 4 5 6 7 8 9

输出

39

说明

下标 $5$ 的算子在矩阵计算单元的执行时间为 $6$ ，将它部署在向量计算单元，

执行时间变为 $6*6=36$ ，剩下的算子部署在矩阵计算单元，执行时间为 $1+2+3+4+5+7+8+9=39$ 。

总的执行时间为 $39$ ，没有比这执行时间更短的方案了。

样例2

输入

9
3 2 17 8 3 5 4 18 15

输出

66

说明

下标 $3,4$ 的算子在矩阵计算单元的执行时间为 $8,3$ ，将它部署在向量计算单元,

执行时间变为 $8 * 6 + 3 * 6 = 66$ ，剩下的算子部署在矩阵计算单元，执行时间为 $3+2+17+5+4+18+15=64$ ，

总的执行时间为 $66$ ，没有比这执行时间更短的方案了。