There are stones, numbered
. For each
, the height of Stone
is
. Here,
holds.
There is a frog who is initially at 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 stones: 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 will contain two integers .
The second line will contain integers,
.
Output Specification
Print the minimum possible total cost incurred.
Sample Input 1
5 6
1 2 3 4 5
Sample Output 1
20
Explanation For Sample 1
If we follow the path , the total cost incurred would be
.
Sample Input 2
2 1000000000000
500000 1000000
Sample Output 2
1250000000000
Explanation For Sample 2
The answer may not fit into a 32-bit integer type.
Sample Input 3
8 5
1 3 4 5 10 11 12 13
Sample Output 3
62
Explanation For Sample 3
If we follow the path , the total cost incurred would be
.
Comments