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 i curred would be
.
For the fourth sample, if we follow the path , the total cost incurred would be
.
Comments