题目描述

古月一觉醒来，发现自己在一个神奇的世界中。

在这个世界中一共有 $N$ 个异区间，每个异区间的编号依次为 $1,2......N$。古月知道自己想要离开这个奇怪的世界需要抵达第 $N$ 个异区间找到这个世界的生命核心。古月拥有一个特别强大的魂技：空间穿梭。具体来说，假如古月当前在第 $x$ 个异区间，那么她可以消耗 $v_i$ 魂力穿梭到第 $x+i$ 个异区间。显然她不能穿梭出这个世界。古月一开始在第 1 个异区间。现在她想知道自己抵达第 $N$ 个异区间最少需要消耗多少魂力。因为她比较懒，所以她想请你来帮她计算这个问题。

输入

第一行两个正整数 $N$，表示有 $N$ 个异区间。

第二行 $N-1$ 个正整数，其中第 $i$ 个数 $v_i$，表示第一次性向右穿梭 $i$ 个异区间所需要的魂力值。

输出

输出一个整数表示最小需要耗费多少魂力。

样例

5
1 2 4 2

2

样例解释

古月可以选择直接从第 1 个异区间穿梭到第 5 个异区间，需要花费 2 点魂力。

数据范围

$N\le3\times10^3$

$v_i\le10^8,i\in[1,N]$