一年一度的文化节快到了，诗文赏析社的同学想要举办她们自己创作的诗展。诗文赏析社的社长跟书法社的社长是好朋友，于是找来了一些书法社的同学帮忙书写诗文。一开始一切似乎都很顺利，但是负责采购的同学突然发现，用来写书法的纸实在是不便宜！这种纸的计价方式如下：

一首诗共有N 行，第i 行的长度为L_i 个字，而纸只卖长方形的，所以一首诗如果要写在同一张纸上，则必须准备面积(行数 x 宽度) 为N x MAX(L_i) 的纸。 1 单位面积的纸要价 1 元，虽然单位价格不高，但是对于长长的诗来说，这价格还是对学生不友善的。

于是，聪明的学生发现了一件事情，那就是，在她们创作的诗文中，通常只有连续的几行，长度特别长或特别短，而在其他的行里面，长度都不长也不短。因此，采购的学生决定，一首诗就分成三段，写在三张纸上好了！这三张纸分别为N₁ x H₁, N₂ x H₂ 及N₃ x H3，因为这三张纸的宽度很可能不会三者都必须要是MAX(L_i) ，因此理论上可以省下不少钱！

但是，老板觉得，要准备三种宽度不同的纸实在是太麻烦了！所以黑心的老板给了另外一个规定，那就是 H₁ 必须要跟 H₃ 一样！

举例来说，假设一首六行诗文每行的长度依序为[3, 3, 7, 7, 4, 3]，那第三张纸可以选择2 x 4, 2 x 7  及2 x 4 的纸，这样三张纸加起来只要30 元，比起单一一张6 x 7 的纸足足省下了12 元呢！注意在这个例子中，第一张纸不能是 2 x 3，因为这样虽然写的下，但是不满足 H₁ = H₃ 的条件。

现在，给定一首诗每行的长度，请问这种策略下，最少需要花费多少钱买纸呢？

请注意，N₁, N₂ 及 N₃ 这三个整数中，可以有一些是 0。

因为诗真的可能很长很长，所以输入的方式不会直接给出每行的长度，而是会给出一些generator的参数，用来产生出这些诗文每行的长度。关于generator的算法及参数请详阅输入说明。