Submit solution

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

Problem type

There are N stones numbered 1, 2, ..., N. For each i (1 \le I \le N), the height of Stone i is h_i.

There is a frog who is initially on Stone 1. He will repeat the following action some number of times to reach Stone N:

If the frog is currently on Stone i, jump to one of the following: Stone i + 1, i + 2,..., i + K. Here, a cost of |h_i - h_j| is incurred, where j is the stone to land on.

Find the minimum possible total cost incurred before the frog reaches Stone N.

Constraints

  • All values in input are integers.
  • 2 \le N \le 10^5
  • 1 \le K \le 100
  • 1 \le h_i \le 10^4

Input Specification

The first line of input will contain 2 integers N and K.

The second line of input will contain N spaced integers, h_i the height of stone i.

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 1 \rightarrow 2 \rightarrow 5, the total cost incurred would be |10 - 30| + |30 - 20| = 30.

For the second sample, if we follow the path 1 \rightarrow 2 \rightarrow 3, the total cost incurred would be |10 -30| + |30 - 20| = 30.

For the third sample, if we follow the path 1 \rightarrow 2, the total cost i curred would be |10 - 10| = 0.

For the fourth sample, if we follow the path 1 \rightarrow 4 \rightarrow 8 \rightarrow 10, the total cost incurred would be |40 - 70| + |70 - 70| + |70 - 60| = 40.


Comments

There are no comments at the moment.