## Frog

View as PDF

Points: 20
Time limit: 2.0s
Memory limit: 64M

Problem type

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 .