There are stones, numbered . For each , the height of Stone is .
There is a frog who is initially on Stone . He will repeat the following action some number of times to reach 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 and .
The second line of input will contain spaced integers, , the height of stone .
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 , the total cost incurred would be .
For the second sample, if we follow the path , the total cost incurred would be .
For the third sample, if we follow the path , the total cost incurred would be .
For the fourth sample, if we follow the path , the total cost incurred would be .
Comments
pypy is recommended for python submissions to not TLE