There are
There is a frog who is initially on Stone
- If the frog is currently on Stone
, jump to one of the following: Stone . Here, a cost of is incurred, where is the stone to land on.
Find the minimum possible total cost incurred before the frog reaches Stone
Constraints
- All values in input are integers.
Input Specification
The first line of input will contain 2 integers
The second line of input will contain
Output Specification
Output a single integer, the minimum possible total cost incurred.
Sample Input 1
5 3
10 30 40 50 20
Sample Output 1
30
Sample Input 2
3 1
10 20 10
Sample Output 2
20
Sample Input 3
2 100
10 10
Sample Output 3
0
Sample Input 4
10 4
40 10 20 70 80 10 20 70 80 60
Sample Output 4
40
Sample Explanations
For the first sample, if we follow the path
For the second sample, if we follow the path
For the third sample, if we follow the path
For the fourth sample, if we follow the path
Comments
pypy is recommended for python submissions to not TLE