## Educational DP Contest AtCoder B - Frog 2

View as PDF

Points: 7
Time limit: 1.0s
Memory limit: 1G

Problem type

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 .