stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;





const int nax = 1e5+103;

int n, k;

int dp[nax];

int a[nax];

int f(int i){

	if (i==n-1) return 0;

	if(dp[i]!=-1) return dp[i];

	int ans = abs(a[i]-a[i+1])+f(i+1);

	for(int j=2; j<=k; j++){

		if(i+j<n) ans = min(ans, abs(a[i]-a[i+j])+f(i+j));

	}

	return dp[i]=ans;

}

int main(){

	cin>>n>>k;

	for(int i=0; i<n; i++) cin>>a[i];

	memset(dp, -1, sizeof dp);

	cout<<f(0)<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.3832331584514987x):
#include<bits/stdc++.h>

using namespace std;







int main() {

    ios_base::sync_with_stdio(false);



    long long int a,b,c,d,i,j,k,n,m;

    cin>>n>>k;

    long long int ar[n+1],dp[n+1];

    for(i=0;i<n;i++)

        cin>>ar[i];

     dp[0]=0;

     for(i=1;i<n;i++)

        dp[i]=INT_MAX;

    //dp[1]=abs(ar[1]-ar[0]);

    for(i=0;i<n;i++)

    {

        //a=INT_MAX;

        for(j=1;j<=k && i+j<n;j++)

        {

           c=i+j;

           dp[c]=min(dp[c],(dp[i]+abs(ar[i]-ar[c])));

           //cout<<i<<" "<<c<<" "<<dp[0]<<" "<<dp[c]<<"\n";

        }





    }

    cout<<dp[n-1]<<"\n";

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



#define y1 as214

#define ii pair < int , ll >

#define iii pair < int , ii >

#define iv pair < ii , ii >



#define fi first

#define se second

#define fr front()

#define pb push_back



#define FOR(i , x , n) for(int i = x ; i <= n ; ++i)

#define REP(i , n) for(int i = 0 ; i < n ; ++i)



#define ll long long

#define oo INT_MAX



/// dp[i] là quãng đường dài nhất để xuất phát từ 1 và kết thúc tại i.



const int N = 1e5 + 5;

ll n , k;

ll dp[N] , f[N];



int main()

{

    ios::sync_with_stdio(0);

    cin.tie(0);

    cin >> n >> k;

    FOR(i , 1 , n)

        cin >> f[i];

    memset(dp , 0x1f , sizeof(dp));

    dp[1] = 0;

    FOR(i , 2 , n)

    {

        FOR(j , max((ll)1 , i - k) , i - 1)

            dp[i] = min(dp[i] , dp[j] + abs(f[i] - f[j]));

    }

    cout << dp[n] << endl;

}


// Faster C++ solution for the same problem (measured speedup: 1.8087762148420616x):
#include<bits/stdc++.h>

using namespace std;



#define y1 as214

#define ii pair < int , int >

#define iii pair < int , ii >

#define iv pair < ii , ii >



#define fi first

#define se second

#define fr front()

#define pb push_back

#define t top()



#define FOR(i , x , n) for(int i = x ; i <= n ; ++i)

#define REP(i , n) for(int i = 0 ; i < n ; ++i)

#define FORD(i , x , n) for(int i = x ; i >= n ; --i)



#define ll long long

#define oo 1e17

#define int long long



const int N = 1e5 + 5;

int n , k;

int dp[N] , a[N];

/// dp[i] là giá nhỏ nhất để tới được hòn đá thứ i.



main()

{

    //freopen("B.inp","r",stdin);

    ios::sync_with_stdio(0);

    cin.tie(0);

    cin >> n >> k;

    FOR(i , 1 , n)

        cin >> a[i];

    FOR(i , 2 , n)

    {

        dp[i] = 1e16;

        FOR(j , max((ll)1 , i - k) , i - 1)

            dp[i] = min(dp[i] , dp[j] + abs(a[i] - a[j]));

    }

    cout << dp[n];

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;

using ll =long long;

using db = double;



template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }



#define che(a,string) cout<<"//"<<string <<"=="<<(a)<<"//" <<endl;

#define SORT(a) sort((a).begin(),(a).end())

#define rSORT(a) reverse((a).begin(),(a).end())

#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)

#define rep(i, n)       For(i, 0, n)

#define leftunique(v) SORT(v);(v).erase(unique((v).begin(),(v).end()),(v).end())

//leftuniqueは配列から同じ要素のものを取り除く 例 4 6 2 1 3 4 1 2 なら 1 2 3 4 6 になる

bool IsInt(double a){int b = a/1;if(a==b){return true;}else {return false;}}

bool coY() {cout <<"Yes"<<endl;}

bool coN(){cout <<"No"<<endl;}

const int mod = 1e9 + 7;

const ll INF = 1LL << 60;



//ここから書き始める

int main()

{

	cout << setprecision(10);

	ll n, k;

	cin >> n >> k;

	vector<ll> h(110010);

	rep(i,n) cin >> h[i];



	vector<ll> dp(110010,INF);

	dp[0] = 0;

	rep(i,n){

		For(j,1,k+1){

			chmin(dp[i+j],dp[i]+abs(h[i] - h[i+j]));

		}

	}

	

	

	cout<<dp[n-1]<<endl;



}


// Faster C++ solution for the same problem (measured speedup: 1.5261585339723192x):
#include <bits/stdc++.h>



using namespace std;

using ll =long long;

using db = double;



template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }



#define che(a,string) cout<<"//"<<string <<"=="<<(a)<<"//" <<endl;

#define SORT(a) sort((a).begin(),(a).end())

#define rSORT(a) reverse((a).begin(),(a).end())

#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)

#define rep(i, n)       For(i, 0, n)

#define leftunique(v) SORT(v);(v).erase(unique((v).begin(),(v).end()),(v).end())

//leftuniqueは配列から同じ要素のものを取り除く 例 4 6 2 1 3 4 1 2 なら 1 2 3 4 6 になる

bool IsInt(double a){int b = a/1;if(a==b){return true;}else {return false;}}

bool coY() {cout <<"Yes"<<endl;}

bool coN(){cout <<"No"<<endl;}

const int mod = 1e9 + 7;

const ll INF = 1LL << 60;



//ここから書き始める

int main()

{

	cout << setprecision(10);

	ll n ,k ;

	cin >> n >> k;

	vector<ll> h(n);

	rep(i,n) cin >>h[i];



	vector<ll> dp(101000,INF);



	dp[0]=0;

	for(int i = 0; i < n; i ++){

		for(int j = 1; j <= k ; j++){

			chmin(dp[i+j], dp[i] + abs( h[i] - h[i+j]));

		}

	}

	cout << dp[n-1] << endl;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

long long n,h[100010],dp[100010],k;



int main()

{

	scanf("%lld %lld",&n,&k);

	for(int i=1;i<=n;i++)

	{

		scanf("%lld",&h[i]);

	}

	for(int i=2;i<=n;i++)

	{

		for(int j=1;j<=k;j++)

		{

			if(i>j)

			{

				if(j==1)dp[i] = dp[i-j]+abs(h[i-j]-h[i]);

				else dp[i] = min(dp[i],dp[i-j]+abs(h[i-j]-h[i]));

			}

		}

	}

	printf("%lld\n",dp[n]);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.6599842544176933x):
#include <cstdio>

#include <algorithm>

#include <cmath>

using namespace std;



int h[(int)1e5], dp[(int)1e5], K, N;





int main()

{

	K = N = 0;

	for(int j = 1;j <= 1e5;j++)

	{

		dp[j] = 1e9;

	}

	scanf("%d %d", &N, &K);

	for(int i = 1;i <= N;i++)

	{

		scanf("%d", &h[i]);		

	}

	dp[1] = 0;

	dp[2] = dp[1] + abs(h[1] - h[2]);

	for(int i = 1;i <= N;i++)

	{

		for(int j = 1;j <= K;j++)		

		{

			dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]));

		}

	}

	printf("%d\n", dp[N]);

	return 0;	

}
// Slower C++ solution:
#include <iostream> 

#include <algorithm> 

#include <vector> 



const int inf=0x3f3f3f3f;

using namespace std; 

int main()

{

  ios::sync_with_stdio(false); 

  cin.tie(0); cout.tie(0); 

  int n,k; 

  cin>>n>>k;

  vector <int> a(n);  

  for (int i=0; i<n; i++) cin>>a[i]; 

  vector <int> dp(n, inf); dp[0]=0; 

  for (int i=0; i<n; i++){

    for (int j=1; j<=k && (i+j)<n; j++){

      dp[i+j]=min(dp[i+j],dp[i]+abs(a[i+j]-a[i]));   

    }

  }

  cout<<dp[n-1]<<"\n"; 

  return 0; 

}

// Faster C++ solution for the same problem (measured speedup: 5.345926050152161x):
#include <stdio.h>

using namespace std;

#define MAX(a,b) (a>b?a:b)

#define MOD(a) (a>0?a:-(a))

#define custoate(i)

int main(){

  int npedras, maxpulo;

  scanf("%d %d",&npedras,&maxpulo);

  int hpedra[npedras],custoate[npedras];

  for (size_t i = 0; i < npedras; i++)

    scanf("%d", &hpedra[i]);

  custoate[0] = 0;

  int tempcost = 2147483647,k,tempcost2;

  for (size_t i = 1; i < npedras; i++,tempcost = 2147483647) {

    // printf("i = %d, tempcost = %d\n", i,tempcost);

    for (k= (maxpulo>i ? i : maxpulo); k > 0; k--) {

      // printf("k = %d ",k);

      tempcost2 = custoate[i-k] + MOD(hpedra[i-k]-hpedra[i]);

      if (tempcost > tempcost2)

        tempcost = tempcost2;

    }

    // printf("custo[%d] = %d",i,tempcost);

    custoate[i] = tempcost;

    // printf("\n\n");

  }

  printf("%d\n", custoate[npedras-1]);



}
// Slower C++ solution:
#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <iostream>

#define MAXN 50100

using namespace std;

int x[MAXN],y[MAXN];

struct edge{

	int from,to;double quan;

}e[MAXN*2];

int n,m;int fa[MAXN];



int find(int x){

	if(fa[x]!=x) fa[x]=find(fa[x]);

	return fa[x];

}



double getdis(int f,int s){

	return sqrt((x[f]-x[s])*(x[f]-x[s])+(y[f]-y[s])*(y[f]-y[s]));

}



bool cmp(edge x,edge y){

	return x.quan>y.quan;

}



int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++) cin>>x[i]>>y[i];//scanf("%f%f",&x[i],&y[i]);

	double ans=0;

	for(int i=1;i<=n;i++) fa[i]=i;

	for(int i=1;i<=m;i++){

		int xx,yy;scanf("%d%d",&xx,&yy);

		double dis=getdis(xx,yy);

		e[i].from=xx,e[i].to=yy,e[i].quan=dis;

		ans+=dis;

	}

	sort(e+1,e+m+1,cmp);

	for(int i=1;i<=m;i++){

		int xx=find(e[i].from),yy=find(e[i].to);

		if(fa[xx]!=fa[yy]){

			fa[xx]=yy;

			ans-=e[i].quan;

		}

	}

	printf("%0.3f",ans);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.732508341262494x):
#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>



using namespace std;



int n, m, f[10010], x[10010], y[10010];

double ans = 0.0;



struct edge {

	int u, v;

	double w;

	bool operator < (const edge &b) const { return w < b.w; }

}e[1000010];



double getdis(int u, int v) {

	return sqrt((double)(x[u] - x[v]) * (x[u] - x[v]) + (double)(y[u] - y[v]) * (y[u] - y[v]));

}



int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }



int main() {

	scanf("%d%d", &n, &m);

	for(int i = 1; i <= n; ++i) {

		f[i] = i;

		scanf("%d%d", &x[i], &y[i]);

	}

	int u, v;

	for(int i = 1; i <= m; ++i) {

		scanf("%d%d", &u, &v);

		e[i].u = u;

		e[i].v = v;

		e[i].w = getdis(u, v);

	}

	sort(e + 1, e + m + 1);

	for(int i = m; i >= 1; --i) {

		int fu = find(e[i].u);

		int fv = find(e[i].v);

		if(fu != fv) f[fu] = fv;

		else ans += e[i].w;

	}

	printf("%.3lf\n", ans);

	return 0;

}
// Slower C++ solution:
#include "bits/stdc++.h"

using namespace std;



#define MIN(x, y) ((x) < (y) ? (x) : (y))

#define MAX(x, y) ((x) > (y) ? (x) : (y))



#define DIVUP(x, y) (((x) + ((y) - 1)) / (y))

#define DIVOFF(x, y) (((x) + ((y) / 2)) / (y))

#define REMAINDER(x, y) ((x) % (y))



int N;

long ans{1};



int main() {

  scanf("%d", &N);

  for (int i{1}; i <= N; ++i) {

    ans *= i;

    ans %= 1000000007;

  }



  printf("%ld\n", ans);

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.4907942927791114x):
//#include "bits/stdc++.h"

//using namespace std;

#include <stdio.h>



#define MIN(x, y) ((x) < (y) ? (x) : (y))

#define MAX(x, y) ((x) > (y) ? (x) : (y))



#define DIVUP(x, y) (((x) + ((y) - 1)) / (y))

#define DIVOFF(x, y) (((x) + ((y) / 2)) / (y))

#define REMAINDER(x, y) ((x) % (y))



int N;

long ans{1};



int main() {

  scanf("%d", &N);

  for (int i{1}; i <= N; ++i) {

    ans *= i;

    ans %= 1000000007;

  }



  printf("%ld\n", ans);

  return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define mem(x,v) memset(x,v,sizeof(x)) 

#define go(i,a,b)  for (int i = a; i <= b; i++)

#define og(i,a,b)  for (int i = a; i >= b; i--)

#define MID(a,b) (a + b) >> 1

#define lson now << 1

#define rson now << 1 | 1

#define low(x) (x & (-x))

using namespace std;

typedef long long LL;

const double EPS = 1e-10;

const int INF = 1e9+100;

const int N = 1e6+10;

int a[N],b[N],c[N];

LL f[N];

int n,tt;

void Add(int x){

	while(x <= 5*n){

		f[x] += 1;

		x += low(x);

	}

}

int Query(int x){

	int ans = 0;

	while(x > 0) ans += f[x], x -= low(x);

	return ans; 

}

bool find(int k){

	mem(f,0);

	LL Ans = 0;	b[0] = 0;

	go(i,1,n) if (a[i] >= c[k]) b[i] = b[i-1] + 1; else b[i] = b[i-1];

	go(i,0,n) {

		b[i] = 2*b[i] - i + n + 1;

		Ans += Query(b[i]);

		Add(b[i]);

	}

	LL t = (1LL * n * (n + 1)) / 2;

	if (Ans >= (t+1)/2) return 1; 

	return 0;

}



int main(){

	scanf("%d",&n);

	int l = 1, r = n;

	go(i,1,n){

		scanf("%d",&a[i]);

		c[i] = a[i];

	}

	sort(c+1,c+n+1);

	int ans = 0;

	while(l <= r){

		int mid = MID(l,r);

		if (find(mid)) l = mid+1,ans = c[mid]; else r = mid - 1;

	}

	printf("%d\n",ans);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.8507521997974208x):
#include <bits/stdc++.h>

using namespace std;

int n, a[100005], sum[100005];

long long m;

namespace BIT

{

	long long c[500005];

	inline long long lowbit(long long x) { return x & (~x + 1); }

	inline void add(long long x, long long val)

	{

		for (long long i = x; i < 4 * n; i += lowbit(i))	c[i] += val;

	}

	inline long long sum(long long x)

	{

		long long res = 0;

		for (long long i = x; i; i -= lowbit(i))	res += c[i];

		return res;

	}

}

bool check(int x)

{

	long long cnt = 0;

	sum[0] = 0;

	for (int i = 1; i <= n; ++i)

	{

		sum[i] = (a[i] >= x);

		sum[i] += sum[i - 1];

	}

	for (int i = 0; i <= n; ++i)

	{

		sum[i] = (2 * sum[i] - i) + n + 1;

	}

	memset(BIT::c, 0, sizeof(BIT::c));

	for (int i = 0; i <= n; ++i)

	{

		cnt += BIT::sum(sum[i]);

		BIT::add(sum[i], 1);

	}

	return cnt >= (m+1)/2;

}

int main()

{

	int l = 1000000005, r = 1, ans, mid;

	scanf("%d", &n);

	m = 1ll*n * (n + 1) / 2;

	for (int i = 1; i <= n; ++i)

	{

		scanf("%d", a + i);

		l = min(l, a[i]);

		r = max(r, a[i]);

	}

	while (l <= r)

	{

		mid = (l + r) >> 1;

		if (check(mid))	l = mid + 1, ans = mid;

		else r = mid - 1;

	}

	printf("%d\n", ans);

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define db(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<'\n'

const int N = 1e5;

int A[N+7], dp[N+7], n,k;

const int inf=1e9;



int solve(int i) {

	if(i==n) return 0;

	if(i>n) return inf;

	if(dp[i]!=-1) return dp[i];

	int mn = 2*inf;

	for(int j=1;j<=k;++j) {

		int a = solve(i+j) + abs(A[i]-A[i+j]);

		mn = min(a, mn);

	}

	return dp[i] = mn;

}

int main(){

	ios_base::sync_with_stdio(0);

	int a,b,T,cas=0;

	cin>>n>>k;

	for(int i=1;i<=n;++i) cin>>A[i];

	fill(dp, dp+n+1, -1);

	int res = solve(1);

	cout<<res<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.290690944136945x):
#include<cstdio>

#include<algorithm>

using namespace std;



#define ll long long 



#define file_io 0



ll i,t,j;

ll n,k,h[100005],dp[100005];



int main(){

	if (file_io){

		freopen(".in","r",stdin);

		freopen(".out","w",stdout);

	}

	

	scanf("%lld%lld",&n,&k);

	

	for (i=1; i<=n; ++i){

		scanf("%lld",&h[i]);

	}

	

	dp[1]=0;

	for (i=2; i<=n; ++i){

		dp[i]=2e9;

		for (t=max(1ll,i-k); t<i; ++t){

			dp[i]=min(dp[t]+abs(h[i]-h[t]),dp[i]);

		}

	}

	

	printf("%lld\n",dp[n]);

	

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



#define PB push_back

#define MP make_pair

#define f first

#define s second

#define FOR(i,a,b) for (int i = a; i < b; ++i)

#define RFOR(i, b, a) for (int i = b-1; i>=a; --i)

#define FILL(a, b) memset(a, b, sizeof a)

#define ALL(a) a.begin(), a.end()

#define SZ(a) (int)a.size()



typedef long long LL;

typedef pair<int, int> PII;

typedef vector<int> VI;

typedef vector<LL> VLL;

typedef pair<LL, LL> PLL;



const int INF = 1000 * 1000 * 1000;

const LL LINF = 1LL * INF*INF;

const int MAX = 100010;

const long double PI = acos(-1.);

const double EPS = 1e-6;

LL mod = 1000LL*1000*1000 + 7;



VI g[100*1000+7];

int u[100*1000+7];

int dfs(int v,int v2)

{

	if(v==v2)

		return 1;

	u[v] = 1;

	FOR(i,0,SZ(g[v]))

		if(!u[g[v][i]])

			return dfs(g[v][i],v2);

	return 0;

}



int main()

{

	ios_base::sync_with_stdio(0); double startClock = clock();

//	freopen("input.txt", "r", stdin);

//	freopen("output.txt", "w", stdout);

	int n;

	cin >> n;

	VI arr(n);

	FOR(i,0,n)

	{

		cin >> arr[i];

	}

	VI res;

	FOR(i,0,n)

	{

		int cnt = 0;

		int pos = -1;

		FOR(j,0,n)

		{

			if(arr[j]==-1) continue;

			cnt++;

			if(arr[j]==cnt)

				pos = j;

		}

		if(pos==-1)

		{

			cout << -1;

			return 0;

		}

		res.PB(arr[pos]);

		arr[pos] = -1;

	}

	reverse(ALL(res));

	FOR(i,0,n)

		cout << res[i] << endl;















	cerr << endl << (clock() - startClock)/CLOCKS_PER_SEC << endl;return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.5752479181679937x):
#include<bits/stdc++.h>

using namespace std;

int main()

{

	int n;

	cin>>n;

	int a[n+1],b[n+1];

	for(int i=1;i<=n;i++)

	{

		cin>>a[i];

	}

	int index=1;

	int N=n;

	for(int i=n;i>=1;)

	{

		if(a[i]==i)

		{

			b[index]=a[i];

			index++;

			for(int j=i;j<=n;j++)

			{

				a[j]=a[j+1];

			}

			n--;

			i=n;

		}

		else

		{

			i--;

		} 

	}

	if(index-1==N)

	{

		for(int i=N;i>=1;i--)

		{

			cout<<b[i]<<endl;

		}

	}

	else

	{

		cout<<"-1"<<endl;

	}

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n, a[200009], dp[200009],k;

ll f(int i) {

	if (i > n)return 1e9;

	else if (i == n)return 0;

	if (dp[i] != -1)return dp[i];

	ll ans= f(i + 1) + abs(a[i] - a[i + 1]);

	for(int j=2;j<=k;j++){

            ans=min(ans, f(i+j)+abs(a[i]-a[i+j]));

	}

	return dp[i] =ans;

}

int main() {

	memset(dp, -1, sizeof dp);

	cin >> n>>k;

	for (int i = 1; i <= n; i++) cin >> a[i];

	cout << f(1) << endl;

}


// Faster C++ solution for the same problem (measured speedup: 2.611131550716501x):
#include <bits/stdc++.h>

using namespace std;

int n,a[100009],dp[100009],k;

int main() {

    cin>>n>>k;

    for(int i=1;i<=n;i++){

        cin>>a[i];

         if(i>=2){

         dp[i]=abs(a[i]-a[i-1])+dp[i-1];

            for(int j=1;j<=k;j++){

                    if((i-j)==0)break;

                dp[i]=min(abs(a[i]-a[i-j]) +dp[i-j],dp[i]);

            }

         }

    }

    cout<<dp[n]<<endl;

}
// Slower C++ solution:
#include <iostream>

using namespace std;



template<class T>

inline bool chmin(T &a, T b) {

  if (a > b) {

    a = b;

    return true;

  }

  return false;

}



constexpr int MAX_N = 1e5+100+7;

constexpr int INF = 1e9+7;



int h[MAX_N];

long long dp[MAX_N];



int main() {

  int N, K;

  cin >> N >> K;

  for (int i{}; i < N; ++i) {

    cin >> h[i];

  }



  fill(dp, dp+MAX_N, INF);

  dp[0] = 0;

  for (int i{0}; i < N; ++i) {

    for (int j{1}; j <= K; ++j) {

      if (i+j >= N)

        break;

      chmin(dp[i+j], dp[i] + abs(h[i+j]-h[i]));

    }

  }



  cout << dp[N-1] << endl;

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.2869899118911994x):
#include <bits/stdc++.h>

using namespace std;



template<class T>

inline bool chmin(T &a, T b) {

  if (a > b) {

    a = b;

    return true;

  }

  return false;

}



static const int MAX_N = 1e5+107;

static const int INF = 1e9+7;



int N, K;

int h[MAX_N];

int dp[MAX_N];



int main() {

  cin >> N >> K;

  for (int i = 0; i < N; ++i) {

    cin >> h[i];

  }



  fill(dp, dp+MAX_N, INF);

  dp[0] = 0;

  for (int i = 0; i < N; ++i) {

    for (int k = 1; k <= K; ++k)

      chmin(dp[i+k], dp[i] + abs(h[i+k] - h[i]));

  }



  cout << dp[N-1] << endl;

  return 0;

}
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <cmath>

#define inf 999999999

using namespace std;

int num;

int main()

{

    int a,b;

    int temp;

    vector<int> cost(1e5+1);

    vector<int> dp(1e5+1);

    while(cin>>a>>b){

        fill(cost.begin(),cost.end(),0);

        fill(dp.begin(),dp.end(),inf);

        for(int i=0;i<a;i++){

            cin>>cost[i];

        }

        dp[0]=0;

        dp[1]=abs(cost[1]-cost[0]);

        for(int i=1;i<a;i++){

            for(int j=1;j<=i && j<=b;j++){

                 dp[i]=min(dp[i],dp[i-j]+abs(cost[i-j]-cost[i]));

            }

        }

        cout<<dp[a-1]<<endl;

    }

}


// Faster C++ solution for the same problem (measured speedup: 1.9604909322666124x):
#include<bits/stdc++.h>

using namespace std;

int a[100001],dp[100001];

int solve(int n,int k)

{

    dp[0]=0;

    dp[1]=abs(a[0]-a[1]);

    for(int i=2;i<n;i++)

    {

        int c;

        int d=INT_MAX;

        for(int j=max(0,i-k);j<i;j++)

        {

            c=dp[j]+abs(a[i]-a[j]);

            d=min(c,d);

        }

        dp[i]=d;

    }

    return dp[n-1];

}

int main()

{

    int n,k;

    cin >> n >> k;

    for(int i=0;i<n;i++)

    {

        cin >> a[i];

    }

    cout << solve(n,k) << endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

int dp[100100];

int v[100100];

int n, k;

int INF = 1e9 + 100; 



int run(int i) {

	if(i > n - 1) return 0;

	if(dp[i] != -1) return dp[i];

	

	int mn = INF;

	for(int j=1; j<=k; ++j) {

		if (i + j < n - 1) {

			int val = run(i + j);

			mn = min(mn, val + abs(v[i] - v[i + j]));

		} else if(i + j == n - 1) {

			mn = min(mn, abs(v[i] - v[i + j]));

		}

	}

	return dp[i] = mn;

}



int main() {

	cin>>n>>k;

	for(int i=0; i<n; ++i) {

		cin>>v[i];

	}

	memset(dp, -1, sizeof dp);

	

	cout<< run(0) <<endl;

	/*for(int i=0; i<n; ++i) {

		cout<<dp[i]<<" ";

	} cout<<endl;*/

	

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.407881359307178x):
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

const int INF = 1e9;

int n,k;

int h[N];

int dp[N];

int main() {

	scanf("%d %d", &n, &k);

	for(int i = 0; i < n; ++i) {

		scanf("%d", &h[i]);

		dp[i] = INF;

	}

	dp[n - 1] = 0;

	for(int i = n - 2; i >= 0; --i) {

		for(int j = 1; j <= k and i + j < n; ++j) {

			dp[i] = min(dp[i], dp[i + j] + abs(h[i] - h[i + j]));

		}

	}

	printf("%d\n", dp[0]);

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



int main(){

  int s;

  cin >> s;

  vector<int> a(1000000, 0);

  a.at(s)++;

  for(int i=2; i<1000000; i++){

    if(s%2 == 0){

      s /= 2;

      a.at(s)++;

    }else{

      s *= 3;

      s++;

      a.at(s)++;

    }

    if(a.at(s) == 2){

      cout << i << endl;

      break;

    }

  }

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 4.8619531914191985x):
#include <bits/stdc++.h>

using namespace std;



int main(){

  int n;

  cin >> n;

  vector<int> x(10000);

  x.at(0) = n;

  for(int i=1; i<10000; i++){

    if(n%2 == 0){

      n /= 2;

    }else{

      n = 3*n+1;

    }

    for(int j=0; j<i; j++){

      if(n == x.at(j)){

        cout << i+1 << endl;

        return 0;

      }

    }

    x.at(i) = n;

  }

  return 0;

}