跳棋游戏

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　在一行 \(N\) 个格子的棋盘上，每个格子上一个分数（非负整数）。棋盘第 1 格是唯一的起点，第 \(N\) 格是终点，游戏要求玩家控制一个青蛙棋子从起点出发走到终点。

　　玩家每次需要操控青蛙向前跳跃1，2，3或4个格子。 游戏中，青蛙棋子每到达一个格子会消耗一定的体力，起点格子的体力值为0。最终耗费的体力为青蛙棋子从起点到终点过程中到过的所有格子的耗费体力之和。

　　很明显，用不同操控顺序会使得游戏体力值不同，小明想要找到一种耗费体力值最小的一种跳跃方法。

　　现在，告诉你棋盘上每个格子耗费的体力值，你能告诉小明，他控制的棋子最少体力值吗？

【输入格式】

　　第一行包含一个正整数 \(N\)，表示棋盘格子数。
　　第二行包含 \(N\) 个非负整数，\(a_1, a_2, …, a_N\)，其中 \(a_i\) 表示棋盘第 \(i\) 个格子上的体力值，其中\(a_1\) 必然为0。

【输出格式】

　　输出只有一行一个整数，表示最小体力值。

【输入输出样例1】

　Input

9
0 10 14 2 8 3 18 5 17

　Output

22

【数据说明】

　　对于 \(100\%\) 的数据 \(1≤N≤350\)，\(0≤a_i≤100\)。

【来源】

　　Mr.he