题目内容

深度学习算法由一个个计算单元组成，我们称这些计算单元为算子。
对于完成矢量运算的算子我们称为矢量算子。在 NPU 中，矩阵计算单元和向量计算单元都可以执行矢量算子，它们是独立可并行执行的，但它们的计算效率是 6:1，即假设某个矢量算子在矩阵计算单元上执行的时间为 N，则在向量计算单元上执行的时间为 6N。

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

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

1. 单个算子只能部署在矩阵计算单元或向量计算单元；
2. 部署在向量计算单元的算子必须是按照给定顺序连续的。

输入描述

• 第一行：整数 n，表示算子数

• 第二行：该组算子在矩阵计算单元的执行时间 nums

• 1 ≤ n ≤ 10⁴；

• 1 ≤ nums[i] ≤ 10⁴。

输出描述

一个整数，表示该组算子整体的最短执行时间。

样例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；
总的执行时间为 max(39, 36)=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；
总的执行时间为 max(64, 66)=66。没有比这更短的方案。