#1409. 跳岛战术

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Claes

题目描述

“We are the Borg. Resistance is futile.”

博格人在德尔塔象限建立了座超曲速节点。控制了编号为的超曲速节点后,这个超曲速节点可以将战舰送往第座超曲速节点中的任何一座或是从这些节点中的任意一座送回第座节点。现在,Janeway舰长计划驾驶航海家号以最快速度控制这些超曲速节点。

已知这些节点排成了一列,第座节点距上一座节点的距离为。现在,航海家号已经控制了第一座超曲速节点并停泊在此。已知航海家号使用自身的曲速引擎飞过的距离要花费的时间,而使用超曲速节点则消耗的时间。注意:航海家号不能在飞行过程中战斗。由于装备了最新的反博格鱼雷,航海家号可以在抵达一处节点的瞬间控制这座节点。

Janeway舰长参考了著名的“跳岛作战”,计划通过重复如下流程直到完成作战:

1、使用航海家号的引擎飞到未被控制的节点,并控制这一节点。

2、使用超曲速节点前往当前节点之前最近的未被控制的节点,并控制该节点。

3、使用超曲速节点返回编号最大的被控制的节点。

现在,Janeway舰长希望你能告诉她最少需要多长时间才能控制所有的超曲速节点。注意,作战结束时航海家号必须处于编号最大的节点。

输入格式

第一行三个整数。 第二行个整数表示每个节点到上一个节点的距离。

输出格式

一个整数,表示控制所有超曲速节点消耗的时间。

样例

样例输入1

5 2 3
2 3 4 5

样例输出1

40

样例解释1

航海家号不使用超曲速节点,直接依顺序飞过这些节点并进行控制,消耗7+9+11+13=40的时间。

样例输入2

5 1 10
2 3 4 6

样例输出2

49

样例解释2

航海家号先直接飞到4号节点,控制该节点后用超曲速返回3号节点、控制3号用超曲速后返回2号,之后再用超曲速返回4号节点。

随后,航海家号飞到5号节点,并控制这里。

消耗时间19+4+3+7+16=49。

数据范围与提示