stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
/*

	author: Ibrahim-Elsayed (Codeforces Handle)

	date: 8/28/2020

*/



#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pb push_back

const double PI = acos(-1);

const int MOD = 1000000007;



const int mxN = 1e5;

int n, k;

int dp[mxN+1];

int arr[mxN+1];



int go(int i) { // min cost starting from stone i to reach stone n;

	if(i == n) {

		return 0;

	}

	if(i > n) {

		return int(1000000026);

	}

	if(dp[i] != -1) {

		return dp[i];

	}

	int ans = 1000000025;

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

		if(i+kk <= n) ans = min(ans, go(i+kk)+abs(arr[i] - arr[i+kk]));

	}

	return dp[i] = ans;

}



int main() {

	ios::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);



	cin >> n >> k;

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

	memset(dp, -1, sizeof(dp));

	cout << go(1);



	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.3776056364887155x):
/*

	author: Ibrahim-Elsayed (Codeforces Handle)

	date: 9/17/2020

*/

//#pragma GCC optimize("Ofast")

//#pragma GCC target("avx,avx2,fma")

//#pragma GCC optimization("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

typedef long long ll;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const double PI = acos(-1);



int main() {

	ios::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);



	int64_t n, k;

	cin >> n >> k;

	vector<int64_t> arr(n);

	for(int64_t& el : arr) cin >> el;

	vector<int64_t> dp(n, int(1e18));

	dp[n-1] = 0;

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

		for(int kk = 0; kk <= k; kk++) {

			if((i+kk) < n) dp[i] = min(dp[i], dp[i+kk] + abs(arr[i] - arr[i+kk]));

		}

	}

	cout << dp[0] << "\n";



	return 0;

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

#define read(x) scanf("%d",&x)

using namespace std;

typedef long long LL;

const int maxn=5e5+5;

int a[maxn],c[maxn];

int sum[maxn];

int n;

LL tmp;

int lowbit(int x) {

    return x&(-x);

}

int getsum(int x) {

    int sum=0;

    while(x>0) {

        sum+=c[x];

        x-=lowbit(x);

    }

    return sum;

}

void add(int x) {

    while(x<maxn) {

        c[x]+=1;

        x+=lowbit(x);

    }

}

bool check(int x) {

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

    sum[0]=0;

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

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

        else sum[i]=-1;

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

    }

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

        sum[i]+=n+1;

    }

    LL ans=0;

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

        ans+=getsum(sum[i]);

        add(sum[i]);

    }

    if(ans>=tmp)return true;

    else return false;

}

int main() {

    read(n);

    int minn=1e9,maxx=0;

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

        read(a[i]);

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

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

    }

    int l=minn,r=maxx;

    int ans=l;

    tmp=1LL*(n+1)*n/4;

    while(l<=r) {

        int mid=(l+r)/2;

        if(check(mid)) {

            l=mid+1;

            ans=mid;

        }

        else r=mid-1;

    }

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

}


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

#include <cstring>

#include <algorithm>

#define ll long long

#define inf 1<<30

#define il inline 

#define in1(a) read(a)

#define in2(a,b) in1(a),in1(b)

#define in3(a,b,c) in2(a,b),in1(c)

#define in4(a,b,c,d) in2(a,b),in2(c,d)

il void readl(ll &x){

    x=0;ll f=1;char c=getchar();

    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}

    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

    x*=f;

}

il void read(int &x){

    x=0;int f=1;char c=getchar();

    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}

    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

    x*=f;

}

using namespace std;

/*===================Header Template=====================*/

#define N 100010

#define lowbit(x) x&-x

int c[N*10];

int n,a[N],s[N*10];

void add(int x){

    for(int i=x;i<=2*N;i+=lowbit(i))c[i]++;

}

ll query(int x){

    ll sum=0;

    for(int i=x;i>0;i-=lowbit(i))sum+=c[i];

    return sum;

}

bool check(int x){

    for(int i=1;i<=2*N;i++)c[i]=0;

    s[0]=0;

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

        s[i]=s[i-1]+(a[i]>=x?1:-1);

    ll sum=0;

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

        sum+=query(s[i]+N);

        add(s[i]+N);

    }

    return sum>=1ll*n*(n+1)/4;

}

int main(){

    in1(n);

    int l=0,r=0;

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

        in1(a[i]);

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

    }

    int ans=0;

    while(l<=r){

        int mid=(l+r)>>1;

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

        else r=mid-1;

    }

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

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

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring> 

#include<queue>

#include<stack> 

#include<string.h>

#include<set>

#define ll long long

using namespace std;

int main()

{

	int a,b,c;

	while(~scanf("%d%d%d",&a,&b,&c))

	{

		int flag=0;

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

		{

			if((i*a)%b==c%b)

			{

				printf("YES\n");

				flag=1;

				break;

			}

		}

		if(!flag)

		{

			printf("NO\n");

		}

	}

	return 0;

}

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

#include<cmath>



int a,b,c;



int main()

{

	scanf("%d %d %d",&a,&b,&c);

	int flag = 0;

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

		if((b * k + c) % a == 0) {

			printf("YES\n");

			flag = 1;

			break;

		}

	}

	if(!flag) printf("NO\n");

	return 0;

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

using namespace std;



int n, k, x, ans;

int main () {

	

	cin >> n >> k;

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

		cin >> x;

		

		if (x>=k) ans++;

	}

	cout << ans;



return 0;

}

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

int main()

{

	int a,n,k,h[100000],cnt=0;

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

	for(a=0;a<n;a++){

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

		if(h[a]>=k){

			cnt++;

		}

	}

	printf("%d",cnt);

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

using namespace std;



#define clr(arr,val) memset(arr,val ,sizeof arr)

//#define first f

//#define second s



typedef  long long ull;

typedef long long ll;

int const oo=(int)1e9 ;



int const SZ= (int)1e5+1;

//const ll mod=(ll)1e9+7;

int arr[SZ];

int dp[SZ];

int n,k;

//int mn=oo;

int solve(int i){

    

    if(i==n-1)

        return 0;

    if(i>=n)

        return oo;

    

    int &ret=dp[i];

    

    if(ret!=-1)

        return ret;

    ret=oo;

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

        int ch1=abs(arr[i]-arr[i+j])+solve(i+j);

        ret=min(ret,ch1);

        

    }

    return ret;

    

}

int main() {

//    int t ;

//    cin>>t;

//    while(t--){

        cin>>n>>k;

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

                  cin>>arr[i];

        clr(dp,-1);

        cout<<solve(0)<<endl;

//    }

    return 0;

}

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

using namespace std;

int f[200005];

int n,k;

int h[200005];

int main()

{

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

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

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

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

    f[1]=0;	

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

		for(int j=i; j>0 &&(i-j) <= k ;--j)

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

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

	return 0;

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

#include<cstring>

#include<algorithm>

struct node{

	int mins,id1;

	int smin,id2;

}dp[262149];

using std::min;

using std::max;

int n,a[262149];

void merge(int i,int j){

	if(dp[i].mins<dp[j].mins){

		dp[i].smin=max(dp[i].mins,dp[j].smin);

		dp[i].id2=dp[i].mins>dp[j].smin?dp[i].id1:dp[j].id2;

		dp[i].mins=dp[j].mins; dp[i].id1=dp[j].id1;

	}

	else if(dp[i].smin<dp[j].mins&&dp[j].id1!=dp[i].id1)

		dp[i].smin=dp[j].mins,dp[i].id2=dp[j].id1;

	return ;

}

int main(){

	scanf("%d",&n);

	memset(dp,0,sizeof dp);

	for(int i=0;i<(1<<n);++i) scanf("%d",&a[i]);

	dp[0]=(node){a[0],0,-1,-1};

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

		if(dp[i].smin) continue;

		dp[i]=(node){a[i],i,-1,-1};

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

			if((1<<j)&i) merge(i,i^(1<<j));

	}

	int lans=-1;

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

		printf("%d\n",lans=max(lans,dp[k].smin+dp[k].mins));

	}

	return 0;

}

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

using namespace std;



int n, a[(1 << 18) + 5], ans[(1 << 18) + 5];



int main() {

	scanf("%d", &n);

	n = 1 << n;



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

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



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

		int x = a[0], y = 0;

		for(int msk = mask; msk > 0; msk = (msk - 1) & mask) {

			if(a[msk] > x) {

				y = x;

				x = a[msk];

			}



			else if(a[msk] > y)

				y = a[msk];

		}



		ans[mask] = x + y;

	}



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

		ans[i] = max(ans[i - 1], ans[i]);

		printf("%d\n", ans[i]);

	}



	return 0;

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

#include<algorithm>

using namespace std;

int main() {

	int i=0,x,m,n=0;

	cin>>x>>m;

	x=x-1;

	int j=m;

	int s=(2*x)-1;

	int h[s];

	for(i=0;i<x;i++){

		j--;

		h[n]=j;

		n++;

		}

	j=m;

	h[n]=j;

	n++;

	for(i=0;i<x;i++){

		j++;

        h[n]=j;

        n++;

	}

	int k=n;

    sort(h,h+k);

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

        cout<<h[i]<<" " ;

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.219087492517764x):
////sfef

#include<stdio.h>

int main(){



int k,x,i,p,q,r;

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

p=(x-(k-1));

q=(x+(k-2));

r=(x+(k-1));

if(k==1)

{

    printf("%d",x);

}

else{

    for(i=p;i<=q;i++)    

    {

        printf("%d ",i);

    }

    printf("%d",r);

}



return 0;

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



using namespace std;



int v[100005];

int ans[100005];

int n, k;



int main () {

  cin>>n>>k;

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

    int a;

    cin>>a;

    v[i] = a;

  }



  memset(ans, -1, sizeof(ans));

  ans[0]=0;

  

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

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

      int valorNovo = ans[i] + abs(v[i]-v[i+j]);

      

      if (ans[i+j]==-1)

        ans[i+j] = valorNovo;

      else if (ans[i+j]>=valorNovo)

        ans[i+j] = valorNovo;



    }

  }

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



}




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

#include <cmath>

using namespace std;



int SW( int n, int k ){

    int h[n+1], custo[n+1];

    int menor = (1 << 30);

    

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

        cin >> h[i]; 

    }

    

    custo[1] = 0;

    custo[2] = abs(h[2]-h[1]);



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

        menor = (1 << 30);

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

            if( i-j>0 ){

            custo[i]=custo[i-j] + abs(h[i]-h[i-j]);

            }

            if( custo[i]<menor ){

                menor = custo[i];

            }

        }

        custo[i] = menor;

    }



    return custo[n];

}





int main() {

int n,k;



cin >> n >> k;



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



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



using namespace std;



#define F first

#define S second



int N, K;

int H[100005];

int dp[100001];



int main() {

	cin >> N >> K; 

	H[0] = INT32_MAX; // to avoid RTE

	for (int i = 1; i <= N; i++) cin >> H[i];

	for (int i = 0; i <= N; i++) dp[i] = INT32_MAX;

	int ans = 0;

	

	dp[N] = 0; // the base case

	K = min(N - 1, K);

	

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

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

			if (i - j < 0) break;

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

		}

	}



	cout << dp[1] << endl;



	return 0;

}

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

#include <algorithm>

#include <vector>

using namespace std;

 

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

int main(){

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

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

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

	}

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

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

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

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

		}

	}

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

	return 0;

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

using namespace std;



#define ll long long



int dp[100001];

int n, k, arr[100001];

int pound(int pos)

{

    if (dp[pos] != -1)

        return dp[pos];

    

    int mn = INT_MAX;

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

        mn = min(mn, abs(abs(arr[pos] - arr[pos - i - 1])) + pound(pos - i - 1));

    return dp[pos] = mn;

}



int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);



    cin >> n >> k;

    k = min(n, k);



    memset(dp, -1, sizeof(dp));

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

        cin >> arr[i];



    dp[0] = 0;

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

        dp[i] = abs(arr[0] - arr[i]);



    cout << pound(n - 1);



    return 0;

}


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

using namespace std;



#define ll long long



int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);



    int n, k;

    cin >> n >> k;



    k = min(n, k);



    int arr[n], dp[n];



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

    {

        cin >> arr[i];

        

        if (i < k)

            dp[i] = abs(arr[0] - arr[i]);

    }

    

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

    {

        int mn = INT_MAX;



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

            mn = min(mn, abs(arr[i] - arr[i - j - 1]) + dp[i - j - 1]);



        dp[i] =  mn;

    }



    cout << dp[n - 1];



    return 0;

}
// Slower C++ solution:
//**KEEP IT SHORT AND SIMPLE**



#include <bits/stdc++.h>

#define IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define FILES freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

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

#define NL '\n'

#define F first

#define S second

using namespace std;

typedef long long ll;

typedef bool bl;

typedef vector < vector<long long> > vvl;

typedef vector <long long> vll;

typedef pair <long long, long long> pll;

typedef set <long long> sll;

typedef map <long long, long long> mll;

typedef map <long long, bool> mlb;

typedef priority_queue<long long, vector<long long>, greater<long long> > minPq;

double pi = 2 * acos(0.0);

int OO = 0x3f3f3f3f;

long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }

long long lcm(long long a, long long b) { return a * (b / gcd(a, b)); }

ll n, k, arr[100010], dp[100010];

ll solve(ll i)

{

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

    if(~dp[i])      return dp[i];

    ll ans = OO;

    for(int j = i + 1;j <= min(i + k, n - 1);j++)

        ans = min(solve(j) + abs(arr[j] - arr[i]), ans);

    return dp[i] = ans;

}

int main()

{

    IO

    cin >> n >> k;

    REP(i, 0, n)

        cin >> arr[i];

    memset(dp, -1, sizeof dp);

    cout << solve(0);

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.794003092012422x):
//**KEEP IT SHORT AND SIMPLE**



#include <bits/stdc++.h>

#define IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define FILES freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

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

#define NL '\n'

#define F first

#define S second

#define dot(a, b) (conj(a) * (b)).real()

#define cross(a, b) (conj(a)* (b)).imag()

using namespace std;

typedef long long ll;

typedef long double ld;

typedef bool bl;

typedef vector < vector<long long> > vvl;

typedef vector <long long> vll;

typedef pair <long long, long long> pll;

typedef map <long long, long long> mll;

typedef map <long long, bool> mlb;

typedef priority_queue<long long, vector<long long>, greater<long long> > minPq;

typedef tuple<ll, ll, ll> line;

typedef complex<double> point;

const double pi = 2 * acos(0.0);

const int OO = 0x3f3f3f3f;

int main()

{

    IO

    ll n, k;

    cin >> n >> k;

    ll h[n], ans[n];

    REP(i, 0, n)    cin >> h[i];

    ans[0] = 0;

    REP(i, 1, n)

    {

        ll Min = 1e18;

        REP(j, max(i - k, ll(0)), i)

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

        ans[i] = Min;

    }

    cout << ans[n - 1];

    return 0;

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

using namespace std;

const int N=1e5+1;

int n,k,arr[N],dp[N];    



int calc(int idx){

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

    if(idx>n-1)return 1e5;

    

    if(dp[idx]!=-1)

    return dp[idx];

    

    int mn=1e9+10;

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

        mn=min(mn,abs(arr[idx]-arr[i])+calc(i));



    return dp[idx]=mn;

}



int main(){

cin>>n>>k;

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

cin>>arr[i];



memset(dp,-1,sizeof(dp));



cout<<calc(0);

return 0;    

}

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

using namespace std;

const int N=1e5+1;



int main(){

int n,k,arr[N],dp[N];

cin>>n>>k;



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

    cin>>arr[i];

}



dp[0]=0;

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

    int mn=1e9;

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

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

    dp[i]=mn;

}

cout<<dp[n-1];



return 0;    

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

#include <cstring>

#include <cstdio>

#include <string>

using namespace std;

int main(){

    string s,t;

    cin >> s >> t;

    if(s.length() != t.length()){

        cout << "No" << endl;

    }

    else{

        int flag = 0;

        for(int i = 0; i < t.length(); i++){

            if(s == t){

                flag = 1;

                break;

            }

            string tmp = "";

            tmp += s[s.length()-1];

            tmp += s;

            tmp.erase(tmp.length()-1);

            s = tmp;

        }

        if(flag) cout << "Yes" << endl;

        else cout << "No" << endl;

    }

    return 0;

}


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

#include<cstring>



using namespace std;



void exchange(char a[], int left, int right) {

	int i = left, j = right;

	char temp;

	while (i < j) {

		temp = a[i];

		a[i] = a[j];

		a[j] = temp;

		i++;

		j--;

	}

}



void reserve(char a[], int n, int i) {

	exchange(a, 0, i - 1);

	exchange(a, i, n - 1);

	exchange(a, 0, n - 1);

	return;

}



int main() {

	char str[110], str1[110];

	int n, round = 0;

	scanf("%s", str);;

	scanf("%s", str1);

	if (strlen(str) != strlen(str1)) {

		printf("No");

		return 0;

	}

	n = strlen(str);

	while (round <= n) {

		reserve(str, n, 1);

		if (strcmp(str, str1) == 0) {

			printf("Yes");

			return 0;

		}

		round++;

	}

	printf("No");

	return 0;

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

using ll = long long;

using namespace std;



ll dp[100100];

bool vis[100100];

ll n, k, h[100100];



ll func( int pos ) {

    if (pos == n) return 0;

    if (vis[pos]) return dp[pos];

    vis[pos] = 1;



    ll res = 2e9;

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

        res = min(

            res,

            abs(h[pos] - h[j]) + func(j)

        );

    }   



    return dp[pos] = res;

}





int main() {

    ios::sync_with_stdio(false);

    cin >> n >> k;

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



    cout << func( 1 ) << endl;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.288234727614681x):
//才不露白

//还是青蛙跳还是动态规划

//唯一的是你不知道青蛙它从哪跳到了现在的石头上 如果你知道 那就好办了

//比如从k上面跳过来

//dp[i] = dp[k] + abs(h[i] - h[k])

//关键是你k不知道啊

//有想法就好 不用先急着自我否认

//枚举

//dp[1] = 0

//dp[2] = abs(h[2] - h[1])

//写个函数来算看起来不错

//dp[3] = min(从1跳过来,从2跳过来)

//dp[4] = min(从1跳,从2跳，从3跳)用循环 最后求min

//差不多2层吧 先写了试试看

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <math.h>

#include <queue>

#include <stack>

#include <vector>

#include <algorithm>



using namespace std;



const int MAXN = 1e5;

int n,k;

int h[MAXN + 5],dp[MAXN + 5];//



int CHANGE(int i,int k)//

{

	if(i <= k + 1)//一跳就到

	{//从一开始选

		int min = dp[1] + abs(h[i] - h[1]);

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

		{

			if((dp[j] + abs(h[i] - h[j])) < min)

			{

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

			}

		}

		return min;

	}

	else

	{

		int min = dp[i - k] + abs(h[i] - h[i - k]);

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

		{

			if((dp[j] + abs(h[i] - h[j])) < min)

			{

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

			}

		}

		return min;

	}

}



int main()

{

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

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

	{

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

	}

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

	{

		if(i == 1)

		{

			dp[i] = 0;

		}

		else if(i == 2)

		{

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

		}

		else

		{

			dp[i] = CHANGE(i,k);

		}

	}

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

	return 0;

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

using ll = long long;

using namespace std;



ll dp[100100];

bool vis[100100];

ll n, k, h[100100];



int main() {

    ios::sync_with_stdio(false);

    cin >> n >> k;

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



    dp[1] = 0;

    for (int pos = 2; pos <= n; ++pos) {

        ll p = 2e9;

        for (int j = pos - 1; j >= 1 && j >= pos - k; --j)

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

        dp[pos] = p;

    }



    cout << dp[n] << endl;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.285856466871511x):
//才不露白

//还是青蛙跳还是动态规划

//唯一的是你不知道青蛙它从哪跳到了现在的石头上 如果你知道 那就好办了

//比如从k上面跳过来

//dp[i] = dp[k] + abs(h[i] - h[k])

//关键是你k不知道啊

//有想法就好 不用先急着自我否认

//枚举

//dp[1] = 0

//dp[2] = abs(h[2] - h[1])

//写个函数来算看起来不错

//dp[3] = min(从1跳过来,从2跳过来)

//dp[4] = min(从1跳,从2跳，从3跳)用循环 最后求min

//差不多2层吧 先写了试试看

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <math.h>

#include <queue>

#include <stack>

#include <vector>

#include <algorithm>



using namespace std;



const int MAXN = 1e5;

int n,k;

int h[MAXN + 5],dp[MAXN + 5];//



int CHANGE(int i,int k)//

{

	if(i <= k + 1)//一跳就到

	{//从一开始选

		int min = dp[1] + abs(h[i] - h[1]);

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

		{

			if((dp[j] + abs(h[i] - h[j])) < min)

			{

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

			}

		}

		return min;

	}

	else

	{

		int min = dp[i - k] + abs(h[i] - h[i - k]);

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

		{

			if((dp[j] + abs(h[i] - h[j])) < min)

			{

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

			}

		}

		return min;

	}

}



int main()

{

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

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

	{

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

	}

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

	{

		if(i == 1)

		{

			dp[i] = 0;

		}

		else if(i == 2)

		{

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

		}

		else

		{

			dp[i] = CHANGE(i,k);

		}

	}

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

	return 0;

}