Cheapest Way Up the Stairs

Every step of a temple staircase charges a toll: you pay cost[i] coins when you land on step i (the steps are numbered from 0 at the bottom). You start on the ground below step 0 and want to reach the landing above the last step, which is free. Each move takes you up either 1 step or 2 steps.

Write cheapest_climb(cost) that returns the smallest total toll you can pay on the way from the ground to the landing.

Examples

cheapest_climb([10, 1, 10, 1, 10])  # returns 2
cheapest_climb([4, 9, 2])           # returns 6
cheapest_climb([7])                 # returns 0
cheapest_climb([])                  # returns 0

In the first example you land only on steps 1 and 3, paying 1 + 1. In the third, one move of 2 steps takes you from the ground straight to the landing, so you pay nothing.

Constraints

• 0 <= len(cost) <= 500
• 0 <= cost[i] <= 1000