小石腳受傷了,但他被困在湖中央,要出去只能靠一排 N 個橫向等間距、高低不同的石頭。這 N 個石頭分別具有高度 h1,h2,…,hN。
小石在編號 1 的石頭上,他必須跳到編號 N 的石頭上才算逃脫。因為他的腳傷,他縱向跳躍時會感到不適,但橫向則不會。他在一次從第 i 個石頭到第 j 個石頭的跳躍中感受到的不適值是 |hi−hj|。然而他也有跳躍距離限制,當他在石頭 i 時,他只能跳到石頭 i+1,i+2,…,i+K 上。他整段路的不適值是所有跳躍不適值的加總。
對於給定的 N,K 和石頭高度 h1,h2,…,hN,請你求出最小可能的不適值為何。
輸入第一行是兩個以空白分隔的整數,分別代表 N,K。
輸入第二行是 N 個以空白分隔的整數,代表 h1,h2,…,hN。
輸入保證 1≤N≤105,1≤K≤100,1≤hi≤109。
輸出一行一個整數,代表最小走完這段路的不適值。
Atcoder Educational DP Contest