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