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

#pragma GCC optimize "03"

using namespace std;



#define int long long int

#define pb push_back

#define pii pair<int,int>

#define fi first

#define se second

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

#define dbg(x) { cerr<<"> "<<#x<<": "<<x<< endl; }

#define dbg2(x,y) { cerr<<"> "<<#x<<": "<<x<<" , "<<#y<<": "<<y<<endl; }

#define dbg3(x,y,z) { cerr<<"> "<<#x<<": "<<x<<" , "<<#y<<": "<<y<<" , "<<#z<<": "<<z<<endl; }

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

#ifndef LOCAL

#define endl '\n'

#endif

const int inf = INT_MAX;

const double eps = 0.0000001;

const double PI = acos(-1.0);

const int MOD = 1e9+7;

const int N  = 1e5+5;



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



int solve (int i) {

	if (i > n) return inf;

	if (i == n) return 0;

	if (i == n-1) return abs (a[n] - a[n-1]);

	if (dp[i] >= 0) return dp[i];

	int ans = inf;

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

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

	}

	dp[i] = ans;

	return ans;

}



signed main(){

    #ifdef LOCAL

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

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

    #endif  

    IOS;



    cin >> n >> k;

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

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

    	cin >> a[i];

    cout << solve(1);

    return 0;

}

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

#pragma GCC optimize "03"

using namespace std;



#define int long long int

#define pb push_back

#define pii pair<int,int>

#define fi first

#define se second

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

#define dbg(x) { cerr<<"> "<<#x<<": "<<x<< endl; }

#define dbg2(x,y) { cerr<<"> "<<#x<<": "<<x<<" , "<<#y<<": "<<y<<endl; }

#define dbg3(x,y,z) { cerr<<"> "<<#x<<": "<<x<<" , "<<#y<<": "<<y<<" , "<<#z<<": "<<z<<endl; }

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

#ifndef LOCAL

#define endl '\n'

#endif

const int inf = INT_MAX;

const double eps = 0.0000001;

const double PI = acos(-1.0);

const int MOD = 1e9+7;

const int N  = 1e5+5;



int a[N], dp[N];



signed main(){

    #ifdef LOCAL

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

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

    #endif  

    IOS;



    int n, k;

    cin >> n >> k;

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

    	cin >> a[i];

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

    	dp[i] = inf;

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

    		if (i - j >= 1) {

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

    		}

    	}

    }

    cout << dp[n];

    return 0;

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

#include <cstring>

using namespace std;

int dp[100000];

int n,a[100000],k;



int ans(int i)

{

	if(i==n-1)

		return 0;



	if(dp[i]!=-1)

		return dp[i];

  

	int best=1e9;

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

	{

		if(i+j<n)

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

	}

	return dp[i]=best;

}



int main()

{

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

	cin>>n>>k;

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

		cin>>a[i];



	cout<<ans(0)<<endl;



	return 0;

}

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

#include <cstring>

using namespace std;

int dp[100000];

int n,a[100000],k;



int topdown()

{

	dp[n-1]=0;



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

	{

		dp[i]=1e9;

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

		{

          	if(i+j<n)

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

		}

	}

	return dp[0];

}



int main()

{

  	ios_base::sync_with_stdio(0);            //fast input and output

	cin.tie(NULL);

	cout.tie(NULL);

	cin>>n>>k;

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

		cin>>a[i];



	cout<<topdown();



	return 0;

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

using namespace std;

int main()

{

	string s;

	int n;

	cin>>n;

	cin>>s;

	int i=0;

	for(i=0;s[i]!=0;i++);

	if(i<=n)cout<<s;

	else{

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

			cout<<s[t];

		cout<<"...";

	}

}

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

#include<string.h>

int main(){

	int k;

	char s[105];

	scanf("%d",&k);

	getchar();

	scanf("%s",&s);

	if(strlen(s)>k){

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

			printf("%c",s[i]);

		}

		printf("...");

		printf("\n");

	}

	else{

		int l = strlen(s);

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

			printf("%c",s[i]);

		printf("\n");

	}

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

using namespace std;

#define mod 1000000007

#define ll long long int

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);

#define inf 9223372036854775807

#define mini 9223372036854775807

#include <ext/pb_ds/assoc_container.hpp> 

#include <ext/pb_ds/tree_policy.hpp> 

using namespace __gnu_pbds; 

#define ordered_set tree<double, null_type,less<double>, rb_tree_tag,tree_order_statistics_node_update>

pair<ll,ll>s4[4]={{-1,0},{1,0},{0,-1},{0,1}};

pair<ll,ll>s8[8]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,1},{1,0},{1,-1}};

ll power(ll a,ll b)

{

	if(b==0)

		return 1;

	ll c=power(a,b/2);

	if(b%2==0)

		return ((c%mod)*(c%mod))%mod;

	else

		return ((((c%mod)*(c%mod))%mod)*a)%mod;

}

ll n,k;

ll a[200005];

ll dp[200005];

ll func(ll i)

{

	if(dp[i]!=-1)

		return dp[i];

	ll ans1=inf;

	ll ans2=inf;

	if(i==n-1)

		return 0;

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

	{

		if((i+j)<n)

			ans1=abs(a[i+j]-a[i])+func(i+j);

		ans2=min(ans1,ans2);

	}

	dp[i]=min(ans1,ans2);

	return dp[i];

}

int main()

{

	boost

	cin>>n>>k;

	ll i;

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

		dp[i]=-1;

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

		cin>>a[i];

	ll ans=func(0);

	cout<<ans<<endl;

	return 0;

}

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

using namespace std;

#define mod 1000000007

#define ll long long int

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);

#define inf 9223372036854775807

#define mini 9223372036854775807

#include <ext/pb_ds/assoc_container.hpp> 

#include <ext/pb_ds/tree_policy.hpp> 

using namespace __gnu_pbds; 

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>

pair<ll,ll>s4[4]={{-1,0},{1,0},{0,-1},{0,1}};

pair<ll,ll>s8[8]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,1},{1,0},{1,-1}};

ll power(ll a,ll b)

{

	if(b==0)

		return 1;

	ll c=power(a,b/2);

	if(b%2==0)

		return ((c%mod)*(c%mod))%mod;

	else

		return ((((c%mod)*(c%mod))%mod)*a)%mod;

}

ll arr[200005];

ll dp[200005];

int main()

{

	boost

	ll n,k;

	cin>>n>>k;

	ll i;

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

		cin>>arr[i];

	dp[0]=0;

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

	{

		dp[i]=inf;

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

		{

			if(i-j>=0)

			{

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

			}

		}

	}

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

	return 0;

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

using namespace std;

#define ll long long int

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

#define rrep(i,n) for( int i = n; i >= 0; i-- )

#define REP(i,s,t) for( int i = s; i <= t; i++ )

#define RREP(i,s,t) for( int i = s; i >= t; i-- )

#define dump(x)  cerr << #x << " = " << (x) << endl;

#define INF 2000000000

#define mod 1000000007

#define INF2 1000000000000000000





int main(void)

{

    cin.tie(0);

    ios::sync_with_stdio(false);

    bool used[1000010] = {};

    int s; cin >> s;

    int cnt = 1;

    while(true) {

        if (!used[s]) {

            used[s] = true;

            if (s % 2 == 0) s /= 2;

            else s = s * 3 + 1;

        } else {

            cout << cnt << endl;

            return 0;

        }

        cnt++;

    }



    return 0;

}


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

#include <fstream>

#include <set>

#include <map>

#include <string>

#include <vector>

#include <queue>

#include <stack>

#include <functional>

#include <algorithm>

#include <climits>

#include <cmath>

using namespace std;

#define ll long long int

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

#define rrep(i,n) for( int i = n; i >= 0; i-- )

#define REP(i,s,t) for( int i = s; i <= t; i++ )

#define RREP(i,s,t) for( int i = s; i >= t; i-- )

#define dump(x)  cerr << #x << " = " << (x) << endl;

#define INF 2000000000

#define mod 1000000007

#define INF2 1000000000000000000



int cnt[1000010];

int main(void)

{

    cin.tie(0);

    ios::sync_with_stdio(false);

    int s; cin >> s;

    int x = 0;

    while(true) {

        cnt[s]++;

        x++;

        if(cnt[s] == 2) {cout << x << endl; return 0;}

        if(s % 2 == 0) s /= 2;

        else s = s * 3 + 1;

    }



    return 0;

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



using namespace std;

const int N=100000;

int main(){

	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(NULL);

	int n,i,j,k,dp[N],a[N];

	cin>>n>>k;

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

	dp[0]=0;

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

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

	}

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

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

		for(j=2;j<=k;++j) dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]));

	}

	cout<<dp[n-1];

}

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

#include<algorithm>



int main(){

  int s,k;

  long long st[100001],p[100001];

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

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

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

  }

  p[0]=0;

  p[1]=0;

  p[2]=(st[2]-st[1] < 0) ? st[1]-st[2] : st[2]-st[1];

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

    p[i] = 1000000001;

  }

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

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

      if(i-j>=1){

	long long tmp;

	tmp = (st[i]-st[i-j] < 0) ? st[i-j]-st[i] : st[i]-st[i-j];

	if(p[i] > p[i-j]+tmp){

	  p[i] = p[i-j]+tmp;

	}

	if(tmp == 0) break;

      }else{

	break;

      }

    }

  }

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

  return 0;

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

#define ll  long long

#define ld  long double

#define endl "\n"

#define ull  unsigned long long

#define pb push_back

#define all(v) ((v).begin()),((v).end())

#define vi   vector<ll>

#define INF 1000000000

#define M ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);

using namespace std;

int main()

{

	M

	ll n,k,dp[100001]={};

	vi v;

	cin>>n>>k;

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

		ll in; cin>>in; v.pb(in);

	}

	dp[0]=0;

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

		dp[i]=INF;

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

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

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

		}

	}

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

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.8328348529221032x):
#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;

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

using namespace std;

#define INF 100005

#define maxx 1000000000000



int n,k;

long long a[INF+5];

long long mem[INF];



long long rec(int pos)

{

    if(pos==n-1)

    {

        return 0;

    }

    if(mem[pos]!=-1) return mem[pos];

    long long tot=maxx;

    for(int i=pos+1,j=0;i<n && j<k;i++,j++)

    {

        int dis=abs(a[pos]-a[i]);

        tot=min(tot,dis+rec(i));

    }

    return mem[pos]=tot;

}



int main()

{

    memset(a,0,sizeof(a));

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

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

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

    {

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

    }

    long long ans=rec(0);

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

}


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

#define ll long long

#define ull unsigned long long

using namespace std;

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

	

int main (){

	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n >> k;

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

		cin >> a[i];

	}

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

		ll tmp=1e15;

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

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

		}

		if (tmp!=1e15)dp[i]=tmp;

	}

	cout << dp[1] << endl;

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

using namespace std;



typedef vector< long long > vi;

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

#define pb push_back

#define mp make_pair

#define all(c) (c).begin(),(c).end()

#define ll long long



ll cost(ll n, ll h[]);



ll dp[100005];

ll k;



int main(void)

{

    fill_n(dp, 100005, -1);

    ll n;

    dp[1] = 0;

    cin >> n >> k;

    ll h[n];

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

        cin >> h[i];

    

    cout << cost(n, h) << "\n";

}



ll cost(ll n, ll h[])

{

    if (n < 1)

        dp[n] = 1000000000000;

    

    if (dp[n] == -1)

    {

        ll mincost = 1000000000000;

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

            mincost = min(mincost, cost(n - i, h) + abs((h[n - 1] - h[n - i - 1])));

        dp[n] = mincost;

    }

    

    return dp[n];

}

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

using namespace std;



typedef vector <long long> vi;

typedef vector <vi> vvi;

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

#define pb push_back

#define mp make_pair

#define all(c) (c).begin(), (c).end()

#define rall(c) (c).rbegin(), (c).rend()

#define ll long long



int main(void)

{

    ll n, k;

    cin >> n >> k;



    ll h[n];

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

        cin >> h[i];

    

    ll dp[n];

    dp[0] = 0;



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

    {

        dp[i] = LLONG_MAX;

        ll limit = min(k , i);

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

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

    }



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

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



using namespace std;



long long func(long long a) {

    if (a % 2 == 0)

        return a / 2;

    else

        return 3 * a + 1;

}



int main() {

    long long i, s, p, q;

    int a[1000001] = {0};

    cin >> s;

    q = s;

    a[s]++;

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

        long long p = func(q);

        a[p]++;

        if (a[p] == 2) {

            cout << i << endl;

            return 0;

        }

        q = p;

    }



    return 0;

}

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

#include <map>



using namespace std;



int main() {

    int s;

    cin >> s;

    map<int,int> m;

    m[s]++;

    int ans = 2;



    while(1) {

        s = (s % 2 == 0) ? s / 2 : (s * 3 + 1);

        

        m[s]++;

        if (m[s] == 2) {

            cout << ans << endl;

            return 0;

        }

        ans++;

    }



    return 0;

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

using namespace std;

#define fi first

#define se second

#define mp make_pair

#define pb push_back

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

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

#define all(V) V.begin(),V.end()

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

#define de(a) cout<<#a<<" = "<<a<<endl

#define dd(a) cout<<#a<<" = "<<a

typedef long long ll;

typedef pair<int ,int > pii;

typedef vector<int> vi;

//----



const int N=20;

const int mod=1e9+7;

pair<pii,pii> Max[1<<N];

int cmp(pii a,pii b)

{

	return a>b;

}

int main()

{

	int n;

	scanf("%d",&n);

	rep(i,0,1<<n)scanf("%d",&Max[i].fi.fi),Max[i].fi.se=i;

	int Ans=0;

	rep(i,1,1<<n)

	{

		rep(j,0,n)if((i>>j)&1)

		{

			vector<pii> V;

			V.pb(Max[i].fi);

			V.pb(Max[i].se);

			V.pb(Max[i^(1<<j)].fi);

			V.pb(Max[i^(1<<j)].se);

			sort(all(V),cmp);

			V.erase(unique(all(V)),V.end());

			Max[i].fi=V[0],Max[i].se=V[1];

		}

		Ans=max(Ans,Max[i].fi.fi+Max[i].se.fi);

		cout<<Ans<<endl;

	}	

	return 0;	

}

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

using namespace std;

const int d[19]={1,2,4,8,16,32,64,128,256,512,1024,

2048,4096,8192,16384,32768,65536,131072,262144};

int f[262145],g[262145],c[262145],t;

int main()

{

	int n;

	scanf("%d",&n);

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

	g[0]=262144;

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

	{

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

		{

			if (!(i&(1<<j))) continue;

			if (c[f[i]]<c[f[i-(1<<j)]])

			{

				g[i]=f[i];

				f[i]=f[i-(1<<j)];

			}

			else if (f[i]!=f[i-(1<<j)] && c[g[i]]<c[f[i-(1<<j)]]) g[i]=f[i-(1<<j)];

			if (c[g[i]]<c[g[i-(1<<j)]]) g[i]=g[i-(1<<j)];

		}

		if (c[f[i]]+c[g[i]]>c[f[t]]+c[g[t]]) t=i;

		printf("%d\n",c[f[t]]+c[g[t]]);

	}

	return 0;

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

using namespace std;

typedef long long ll;

const ll maxn=4e3+10;

ll n,ans=0,cr=0,cg=0,cb=0;

char s[maxn];

int main(){

	cin>>n>>s;

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

		if(s[i]=='R') ans += cg*cb,cr++;

		if(s[i]=='G') ans += cr*cb,cg++;

		if(s[i]=='B') ans += cr*cg,cb++;

	}

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

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

			if(s[i]!=s[j] && s[i]!=s[j+j-i] && s[j]!=s[j+j-i]) ans--;

		}

	}

	cout<<ans<<endl;

	

}

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

#include<algorithm>



using namespace std;



typedef long long LL;



const int N = 4010;



int r[N], g[N], b[N];

char s[N];



int main()

{

    int n;

    scanf("%d", &n);

    scanf("%s", s + 1);

    

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

    {

        r[i] = r[i - 1], g[i] = g[i - 1], b[i] = b[i - 1];

        if(s[i] == 'R')  r[i] ++;

        else if(s[i] == 'G')  g[i] ++;

        else  b[i] ++;

    }

    

    LL res = 0;

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

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

            if(s[i] != s[j])

            {

                char c = (int)'R' + 'G' + 'B' - s[i] - s[j];

                if(c == 'R')  res += r[i - 1];

                else if(c == 'G')  res += g[i - 1];

                else  res += b[i - 1];

                if(i - (j - i) >= 1 and s[i - (j - i)] == c)  res --;

            }

    printf("%lld\n", res);

    return 0;

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

#include <string>



using namespace std;



int main() {

    char buf[16];

    scanf("%s", buf);

    string s(buf), t;

    for (char c: s) {

        switch (c) {

            case 'B':

                if (!t.empty())

                    t.pop_back();



                break;

            default:

                t.push_back(c);

        }

    }



    printf("%s\n", t.c_str());

    return 0;

}


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



using namespace std;



int main() {

    char s[16], t[16]={};

    scanf("%s", s);



    int j=0;

    for (int i=0; s[i]; ++i) {

        switch (s[i]) {

            case 'B':

                if (j)

                    t[--j] = '\0';



                break;

            default:

                t[j++] = s[i];

        }

    }



    printf("%s\n", t);

    return 0;

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

#define all(v) v.begin(), v.end()

using namespace std;



const int INF = (int)10e9;

int N, K;

vector<int> v;

vector<int> dp;



int main() {

    cin >> N >> K;

    v.resize(N);

    dp.resize(N);

    fill(all(dp), 0);



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

        cin >> v[i];

    }



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

        dp[i] = INF;

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

            if(i - j >= 0) {

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

            }

        }

    }



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



    return 0;

}

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

#define inf 2000000000

int n,k;

int h[100002]={100000},f[100002]={};

int min(int a,int b)

{

	return a<b? a:b;

}

int max(int a,int b)

{

	return a>b? a:b;

}

int abs(int x)

{

	return x<0? -x:x;

}

int main()

{

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

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

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

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

	{

		f[i]=inf;

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

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

	}

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

	return 0;

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

#define LL long long int 

#define LD long double

#define PI 3.14159265358979323846

#define MOD ((LL)1e9+7)

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

using namespace std;

const LL N=1e5+10;

vector<LL>A(N),dp(N);

vector<bool>f(N);

LL n,k;





LL DP(LL I)

{

	if(f[I])return dp[I];

	

	if(I==1)dp[I]=0;

	else

	{

		dp[I]=1e18;

		for(LL j=1;j<=k && I-j>=1;j++)

		dp[I]=min(dp[I],DP(I-j)+abs(A[I]-A[I-j]));

	}

	f[I]=true;

	return dp[I];

	

}



int main()

{

	IOS

	cin>>n>>k;

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

	/*

	dp[1]=0;

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

	{

		LL d=1e18;

		for(LL j=1;j<=k && i-j>=1 ;j++)

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

		dp[i]=d;

	}

	cout<<dp[n]<<endl;*/

	

	cout<<DP(n)<<endl;

		

	

	

}

			

				

			

	

	

	

			

		




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

using namespace std;

#define MOD ((int)(1e9+7))

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

#define int long long

#define float long double



int ans=0,c=0;



int32_t main()

{

	IOS

	int n,k;cin>>n>>k;

	vector<int>H(n+10),dp(n+10,1e15);

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

	dp[1]=0;

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

	{

		for(int j=i-1;j>=max(i-k,1LL);j--)

		{

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

		}

	}

	cout<<dp[n]<<endl;

		

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

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn = 1e5 + 5;

int main(){

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

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

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

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

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

	dp[1] = 0;

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

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

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

		}

	}

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

	return 0;

}

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

using namespace std;

int main()

{

    int n,k;

    cin>>n>>k;

    int h[n];

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

    {

        cin>>h[i];

    }

    long long int dp[n];

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

    dp[0]=0;

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

    {

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

        {

            dp[i+j]=min(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;

int nummer;

vector<long long >dp(100001,900000000000000);

vector<long long>num;

long long  erg(int n){

	if(dp[n]!=900000000000000){

		return dp[n];

	}

	if(n<0){

		return 900000000000000;

	}

	if(n==0){

		return 0;

	}

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

		if(n-i<0){

			break;

		}

		dp[n]=min(dp[n],erg(n-i)+(max(num[n],num[n-i])-min(num[n],num[n-i])));

	}

	return dp[n];

}

int main() {

	int menge,numm;

	cin>>menge>>nummer;

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

		cin>>numm;

		num.push_back(numm);

	}

cout<<erg(menge-1);

    return 0;

}

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

#include <vector>

using namespace std;

int main(){

	int n,k;

	cin>>n>>k;

	vector <int> h(n),dp(n,INT_MAX);

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

	dp[0]=0;

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

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

			if(i+j<n){

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

			}

		}

	}

	cout<<dp[n-1];

	return 0;

}