小美在玩《大富翁》游戏，游戏中有 个城市排成一排，编号从 到 ，第 个城市上有一个数字 ，表示到达第 个城市可以获得 枚金币。 每一轮开始时小美会获得四张卡牌，分别可以跳跃 1、2、3、4 个城市，例如小美可以从城市1跳跃 个城市到达城市4。当小美使用完这 4 张卡牌后，会开启新的一轮。 初始时，小美拥有 枚金币，在任意时刻，小美的金币数量都必须大于等于 ，小美想知道她从第 个城市出发，到达第 个城市最多可以获得多少枚金币。
输入描述:
第一行输入一个整数 表示城市个数。第二行输入 个整数 表示到达城市1到n可以获得的金币数量（第0个城市无法获得金币）。
输出描述:
在一行上输出一个整数表示答案；如果无法到达第 个城市，则输出 。
示例1
输入
10
-1 2 3 4 -9 -9 -1 3 -1 -1
说明
最优的方法是：
第 1 步：使用跳跃 3 的卡牌，从 0 跳到 3 ，获得 3 枚金币；
第 2 步：使用跳跃 1 的卡牌，从 3 跳到 4 ，获得 4 枚金币，共有 7 枚金币；
第 3 步：使用跳跃 4 的卡牌，从 4 跳到 8 ，获得 3 枚金币，共有 10 枚金币；
第 4 步：使用跳跃 2 的卡牌，从 8 跳到 10 ，获得 -1 枚金币，共有 9 枚金币。
加载中...