#AT2. Frog 2

Frog 2

Original Problem Statement (English)

Source: AtCoder Educational DP Contest - Problem B

Problem Statement

There are NN stones, numbered 1,2,…,N1, 2, \ldots, N. For each ii (1≤i≤N1 \leq i \leq N), the height of Stone ii is hih_i.

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

  • If the frog is currently on Stone ii, jump to one of the following: Stone i+1,i+2,…,i+Ki + 1, i + 2, \ldots, i + K. Here, a cost of ∣hi−hj∣|h_i - h_j| is incurred, where jj is the stone to land on.

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

Constraints

  • All values in input are integers.
  • 2≤N≤1052 \leq N \leq 10^5
  • 1≤K≤1001 \leq K \leq 100
  • 1≤hi≤1041 \leq h_i \leq 10^4

Input

Input is given from Standard Input in the following format:

N K
h_1 h_2 \ldots h_N

Output

Print the minimum possible total cost incurred.

Sample Input 1

5 3
10 30 40 50 20

Sample Output 1

30

If we follow the path 11 → 22 → 55, the total cost incurred would be ∣10−30∣+∣30−20∣=30|10 - 30| + |30 - 20| = 30.

Sample Input 2

3 1
10 20 10

Sample Output 2

20

If we follow the path 11 → 22 → 33, the total cost incurred would be ∣10−20∣+∣20−10∣=20|10 - 20| + |20 - 10| = 20.

Sample Input 3

2 100
10 10

Sample Output 3

0

If we follow the path 11 → 22, the total cost incurred would be ∣10−10∣=0|10 - 10| = 0.

Sample Input 4

10 4
40 10 20 70 80 10 20 70 80 60

Sample Output 4

40

If we follow the path 11 → 44 → 88 → 1010, the total cost incurred would be ∣40−70∣+∣70−70∣+∣70−60∣=40|40 - 70| + |70 - 70| + |70 - 60| = 40.