题目描述

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

注意：数组中的最后一个数字并不是楼梯顶部，而是距离楼梯顶部的最后一级台阶，如果走到也要花费。

输入格式

第一行，包含两个正整数 $n$，代表收费楼梯的数量。

接下来的一行，包含 $n$ 个正整数，代表每级台阶收取的费用。

输出格式

一行一个整数，表示走到顶部的最少花费。

样例 #1

样例输入 #1

3
10 15 20

样例输出 #1

15

样例 #2

样例输入 #2

10
1 100 1 1 1 100 1 1 100 1

样例输出 #2

6