TopCoder

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

50.0% (6/12)

Tags

Description

小石腳受傷了,但他被困在湖中央,要出去只能靠一排 $N$ 個橫向等間距、高低不同的石頭。這 $N$ 個石頭分別具有高度 $h_1, h_2, \dots, h_N$。

小石在編號 $1$ 的石頭上,他必須跳到編號 $N$ 的石頭上才算逃脫。因為他的腳傷,他縱向跳躍時會感到不適,但橫向則不會。他在一次從第 $i$ 個石頭到第 $j$ 個石頭的跳躍中感受到的不適值是 $|h_i - h_j|$。然而他也有跳躍距離限制,當他在石頭 $i$ 時,他只能跳到石頭 $i+1, i+2,\dots, i+K$ 上。他整段路的不適值是所有跳躍不適值的加總。

對於給定的 $N,K$ 和石頭高度 $h_1, h_2, \dots, h_N$,請你求出最小可能的不適值為何。

Input Format

輸入第一行是兩個以空白分隔的整數,分別代表 $N, K$。

輸入第二行是 $N$ 個以空白分隔的整數,代表 $h_1, h_2, \dots, h_N$。

輸入保證 $1\le N\le 10^ 5$,$1\le K\le 100$,$1\le h_i\le 10^ 9$。

Output Format

輸出一行一個整數,代表最小走完這段路的不適值。

Sample Input 1

5 2
1 5 3 4 6

Sample Output 1

5

Sample Input 2

7 1
1 5 4 3 2 6 7

Sample Output 2

12

Hints

Problem Source

Atcoder Educational DP Contest

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~15 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2