#AT2. Frog 2

Frog 2

[B] Frog 2(dp_b)

来源: AtCoder Educational DP Contest - Problem B 原题时限:2 秒 / 内存:1024 MB

题目描述

有 NN 块石头,编号为 1,2,…,N1, 2, \ldots, N。

对于每个 ii(1≤i≤N1 \le i \le N),第 ii 块石头的高度为 hih_i。

有一只青蛙初始站在石头 11 上。它会重复下面的动作若干次,直到到达石头 NN:

  • 若青蛙当前位于石头 ii,则跳到石头 i+1,i+2,…,i+Ki+1, i+2, \ldots, i+K 中的任意一块。此时需要支付代价 ∣hi−hj∣|h_i - h_j|,其中 jj 是它落到的石头编号。

求青蛙到达石头 NN 之前所需支付代价总和的最小值。

输入格式

输入由标准输入按以下格式给出:

N K
h_1 h_2 \ldots h_N

输出格式

输出青蛙所需支付代价总和的最小值。

数据范围

  • 输入中的所有值均为整数。
  • 2≤N≤1052 \le N \le 10^5
  • 1≤K≤1001 \le K \le 100
  • 1≤hi≤1041 \le h_i \le 10^4

样例 1

输入:

5 3
10 30 40 50 20

输出:

30

样例 2

输入:

3 1
10 20 10

输出:

20

样例 3

输入:

2 100
10 10

输出:

0

样例 4

输入:

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

输出:

40