stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const int N = 1e5 + 10;

ll dp[1 << 18];

int a[1 << 18];

int main() {

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

    int n, c = 0;

    ll mx;

    cin >> n;

    mx = (1 << n);

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

        cin >> a[i];

    }

    for(int i = 0; i < mx; i++) dp[i] = mx*i;

    ll ans = 0;

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

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

            if((s >> i) & 1) {

                int s0 = s ^ (1 << i);

                ll tmp[4] = {dp[s0]%mx, dp[s0]/mx, dp[s]/mx, dp[s]%mx};

                sort(tmp, tmp + 4, [&](ll x, ll y){return a[x]>a[y];});

                unique(tmp, tmp + 4);

                dp[s] = tmp[0]+tmp[1]*mx;

            }

        }

        ll res = a[dp[s]/mx] + a[dp[s]%mx];

        ans = max(ans, res);

        cout << ans << endl;

    }

    return 0;

}

// Optimized solution to the same problem (faster):
#include <algorithm>

#include <cstdio>

#include <cstring>



#define int long long



const int Maxv = 300010; 



int ans[Maxv], max[Maxv], num, n; 



signed main() {

    scanf("%lld", &n); 

    

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

        scanf("%lld", &num); 

    

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

            ans[j] = std::max(ans[j], max[j] + num); 

            max[j] = std::max(max[j], num); 

        }

    }

       

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

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

        ans[i + 1] = std::max(ans[i + 1], ans[i]); 

    }

    

    return 0; 

}

// Fastest known solution for this problem:
	#include <bits/stdc++.h>

	#define mx 300005

	using namespace std;



	int a[mx], n;

	vector<vector<bool> > vis(mx, vector<bool> (20, false));

	vector<vector<pair<int,int> > > memo(mx, vector<pair<int, int> > (20, {0, 0}));



	void dp(int num, int pos) {

		if(pos == 0) {

			memo[num][0].first = a[num];

			vis[num][0] = true;

			return;

		}

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

 		vector<int> cons;

		dp(num, pos-1);

		cons.push_back(memo[num][pos-1].first);

		cons.push_back(memo[num][pos-1].second);

		if(num & (1<<(pos-1))) {

			dp(num ^ (1<<(pos-1)), pos-1);

			cons.push_back(memo[num ^ (1<<(pos-1))][pos-1].first);

			cons.push_back(memo[num ^ (1<<(pos-1))][pos-1].second);

		}

		sort(cons.begin(), cons.end(), greater<int>());

		memo[num][pos].first = cons[0];

		memo[num][pos].second = cons[1];

		vis[num][pos] = true;

	}



	int main() {

		ios_base::sync_with_stdio(false);

	    cin.tie(NULL);

	    cout.tie(NULL);



		cin >> n;

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

			cin >> a[i];

			

		}

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

			if(!vis[i][n]) {

				dp(i, n);

			}

		}

		int mxv = 0;

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

			mxv = max(memo[i][n].first + memo[i][n].second, mxv);

			cout << mxv << "\n";	

		}

		return 0;

	}
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define N (int)2e5

int n,k,memo[N],c[N];



int dp(int curr) {

    if (curr == n) return 0;

    if (curr > n) return 1e9;

    int &sol = memo[curr];

    if (sol != -1) return sol;

    int keep = INT_MAX;

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

        keep = min(

            dp(curr + i) + abs(c[curr] - c[curr + i]) ,

            keep

        );

    }

    return sol = keep;

}



int main() {

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

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

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

    memset (memo , -1 , sizeof memo);

    printf("%d\n" , dp(1));

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;



int arr[100007];

int dp[100007];



int Solve(int idx, int n, int k){

//	cout<<cost<<" "<<idx<<endl;

	if(idx >= n)return 1e9;

	if(idx == n - 1){

		return 0;	

	}

	

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

	

	int ans = 1e9;

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

		ans = min(ans, abs(arr[idx] - arr[idx+i]) + Solve(idx+i, n, k));

	}

	

	return dp[idx] = ans;

}



int main(){

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

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

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

		

	cout<<Solve(0,n,k)<<endl;

	return 0;

}

// Fastest known solution for this problem:
#include <iostream>

#include <array>

#include <vector>

#include <iomanip>

#include <string>

#include <cmath>

#include <array>

#include <algorithm>

#include <queue>

#include <map>

using namespace std;



typedef  pair<int,int> P;

typedef long long LL;



const LL  INF=1<<31;







int main(){

     int n,k;

     cin>>n>>k;

     int h[100000];

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

          cin>>h[i];

     }

     LL dp[100001];



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

           dp[i]=INF;

      }

            dp[0]=0;

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







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

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

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



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

          }

     }     



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





}
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+1;

vector<int> h(N);

const int INF=1e9+5;

vector<int> dp(N,-1);

int n,k;

int f(int i){

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

    if(i==n) return 0;

    if(i>n) return INF;

    int p = INF;    

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

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

    }

    return dp[i]=p;

}

int main(){

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

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

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

    }

    cout<<f(1)<<'\n';

    // while(1);

    return 0;

}

// Optimized solution to the same problem (faster):
/*

#include "stdafx.h"

#include<iostream>

#include<vector>

#include<algorithm>

#include<queue>

#include<stack>

#include<cmath>

#include<complex>

*/



#include<bits/stdc++.h>



#define X real()

#define Y imag()

#define pb push_back

#define ppb pop_back

#define mp make_pair

#define ff first

#define ss second

#define FastF freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)

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

using ll = long long;

using namespace std;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

typedef vector<int> vi;

typedef vi::iterator vii;

typedef vector<ll> vl;

typedef vl::iterator vli;

typedef long double C;

typedef complex<C> P;

const int INF = 1e9 + 5;

const ll INFF = 1e18 + 5;

const int M = 1e9 + 7;

const double pi = acos(-1);



int main()

{

	//FastF;

	Fast;

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

	vi h(n + 1);

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

		cin >> h[i];

	}

	vi dp(n + 1,INF);

	dp[1] = 0;

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

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

			if (j > n) continue;

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

		}

	}

	cout << dp[n] << '\n';

	return 0;

}

// Fastest known solution for this problem:
#include <iostream>

#include <array>

#include <vector>

#include <iomanip>

#include <string>

#include <cmath>

#include <array>

#include <algorithm>

#include <queue>

#include <map>

using namespace std;



typedef  pair<int,int> P;

typedef long long LL;



const LL  INF=1<<31;







int main(){

     int n,k;

     cin>>n>>k;

     int h[100000];

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

          cin>>h[i];

     }

     LL dp[100001];



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

           dp[i]=INF;

      }

            dp[0]=0;

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







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

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

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



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

          }

     }     



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





}
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

int main()

{

	int n;

	string inp;

	cin>>n;

	getchar();

	cin>>inp;

	long long size=inp.size(),j,i,red=0,green=0,blue=0;

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

		if(inp[i]=='R') red++;

		else if(inp[i]=='G') green++;

		else blue++;

	}

	long long ans=red*green*blue;

	for(i=0 ; i<size-2 ; i++){

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

			long long k=2*j - i;

		//	cout<<i<<" "<<j<<" "<<k<<endl;

			if(k<size){

				if(inp[i]+inp[j]+inp[k]=='R'+'G'+'B') ans--;}

		}

	}

	cout<<ans<<endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 1000000007;



int main()

{

	int n;

	string s;

	cin >> n >> s;



	ll r = 0, g = 0, b = 0;

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

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

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

		else b++;

	}



	ll all = r * g * b;

	ll sub = 0;

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

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

			int k = 2 * j - i;

			if (k < n && s[i] != s[j] && s[j] != s[k] && s[k] != s[i]) sub++;

		}

	}

	cout << all - sub << endl;

}
// Original C++ solution (slower):
#include <iostream>

#include <string>



using namespace std;



int main()

{

    int n;

    string s;

    cin >> n >> s;

    if (s.size()<=n)cout << s;

    else 

    {

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

        {

            cout << s[i];

        }

        cout << "...";

    }

    

    return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>



int main(){

	int k;

	char word[100];

	scanf("%d", &k);

	scanf("%s", &word);

	

	int len = 0;

	

	for(int i = 0; word[i] != '\0'; i++){

		len++;

	}

	

	if(len <= k){

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

	}

	else{

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

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

		}

		printf("...\n");

	}

	return 0;

}

// Fastest known solution for this problem:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 1000000007;

const double PI = acos(-1);



int main()

{

	int k;

	string s;

	cin >> k >> s;

	if (s.size() <= k) cout << s << endl;

	else cout << s.substr(0, k) + "..." << endl;

}
// Original C++ solution (slower):
#include <cstdio>

#include <cstring>

#include <map>

#include <algorithm>

using namespace std;

const int SIZEN = 500010;

int N;

map<long long ,int> mp;

int main(){

	scanf("%d",&N);

	long long ans = 0;

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

		long long x;

		scanf("%lld",&x);

		mp[x]++;

		ans += x;

	}

	int M;

	scanf("%d",&M);

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

		long long x,y;

		scanf("%lld%lld",&x,&y);

		ans -= x * mp[x];

		ans += y * mp[x];

		mp[y] += mp[x];

		mp[x] = 0;printf("%lld\n",ans);

	}

	

	return 0;

}

/*

4

1 1 1 1

3

1 2

2 1

3 5

*/

// Optimized solution to the same problem (faster):
#include <stdio.h>

using namespace std;



int num[100050];



int main()

{

	long long sum=0;

	int N,Q,B,C,a;

	scanf("%d",&N);

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

		num[i]=0;

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

	{

		scanf("%d",&a);

		sum+=(long long)a;

		++num[a];

	}

	scanf("%d",&Q);

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

	{

		scanf("%d%d",&B,&C);

		sum+=(long long)(C-B)*num[B];

		num[C]+=num[B];

		num[B]=0;

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

	}

return 0;

}

// Fastest known solution for this problem:
#include<bits/stdc++.h>

using namespace std;

#define ll long long

#include <string>

const int mxN=1e5;

const int maxN=5e3;

#define ld long double

#define pb push_back

#define mp make_pair

#define ins insert

#define vi vector<int>



int main()

{

    int n;

    cin >> n;

    int cnt[100000]={};

    ll s=0;

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

    {

        int x;

        cin >> x;

        cnt[x-1]++;

        s+=x;

    }

    int q;

    cin >> q;

    while(q--)

    {

        int b,c;

        cin >> b >> c;

        s+=cnt[b-1]*(c-b);

        cnt[c-1]+=cnt[b-1];

        cnt[b-1]=0;

        cout << s << "\n";

    }

}
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int dp[200005];

int a[200005];

int main()

{

    int n,k;

    cin>>n>>k;



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

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

    for(int i=3; i<=n; i++) dp[i]=INT_MAX;

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

    {

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

        {

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

        }



    }

    cout<<dp[n]<<endl;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
#include <iostream>

#include <array>

#include <vector>

#include <iomanip>

#include <string>

#include <cmath>

#include <array>

#include <algorithm>

#include <queue>

#include <map>

using namespace std;



typedef  pair<int,int> P;

typedef long long LL;



const LL  INF=1<<31;







int main(){

     int n,k;

     cin>>n>>k;

     int h[100000];

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

          cin>>h[i];

     }

     LL dp[100001];



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

           dp[i]=INF;

      }

            dp[0]=0;

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







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

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

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



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

          }

     }     



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





}
// Original C++ solution (slower):
#include<iostream>

#include<cstring>

using namespace std;

char a[100001];int b[100001];

int main(){

	cin>>a;

	int n=0;

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

		if(a[i]=='0'){

			b[n]=0;

			n++;

		}

		else if(a[i]=='1'){

			b[n]=1;

			n++;

		}

		else{

			if(n==0)continue;

			else{

				n--;

			}

		}

	}

	for(int i=0;i<=n-1;i++)cout<<b[i];

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

using namespace std;

char s[20], S[20];

int main()

{

	scanf("%s", s);

	int len = strlen(s);

	int cnt = 0;

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

	{

		if(s[i] == '1')

		{

			S[cnt] = '1';

			cnt++;

		}

		if(s[i] == '0')

		{

			S[cnt] = '0';

			cnt++;

		}

		if(s[i] == 'B')

		{

			if(cnt)cnt--;

			S[cnt] = '\0';

		}

	}

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

	return 0;

}


// Fastest known solution for this problem:
#include <bits/stdc++.h>

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

#define pa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};

#define pb push_back



using ll = long long;

using namespace std;

using pint = pair<int,int>;

using pll = pair<ll,ll>;

const int INFint = 1e9;

const ll INFll = 1e18;

ll MOD=1e9+7;



ll gcd(ll a, ll b) { return __gcd(a,b); } //最大公約数

ll lcm(ll a, ll b) { return a/gcd(a,b)*b; } //最大公倍数



// aのn乗をMODで割りながら計算する

ll modpow(ll a, ll n) {

  long long res = 1;

  while (n > 0) {

    if (n & 1) res = res * a % MOD;

    a = a * a % MOD;

    n >>= 1; // right shift

  }

  return res;

}



// MODを法としたaの逆元を計算する

ll modinv(ll a) {

  return modpow(a, MOD - 2);

}



int main(){

  string s;

  cin>>s;

  int N = int(s.size());

  string ans;

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

    //cout << ans << endl;

    if (s[i] == 'B'){

      if (int(ans.size()) != 0){

        ans = ans.substr(0,int(ans.size())-1);

      }

    }else{

      ans += s[i];

    }

  }

  cout << ans << endl;

  return 0;

}
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;



int main() {

  ll n, k;

  cin >> n >> k;

  vector<ll> h(100010, 0);

  vector<ll> dp(100010, 1000000007);



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

    cin >> h[i + 1];

  }



  dp[0] = 0;

  dp[1] = 0;



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

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

      if (i - j > 0) {

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

      }

    }

  }



  cout << dp[n] << endl;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



typedef long long int ll;

ll MOD = 1000000007;

ll INFL = 1ll << 60;

ll INF = 1 << 28;



// ====================================================================

int main() {

  // 入力

  int n, k;

  cin >> n >> k;

  vector<int> v(n);

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

    cin >> v[i];

  }



  vector<ll> dp(n);

  for (int i = 0; i < n; i++) dp[i] = INFL;

  dp[0] = 0;

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

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

      if (i - j < 0) break;

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

    }

  }



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

}


// Fastest known solution for this problem:
#include <iostream>

#include <array>

#include <vector>

#include <iomanip>

#include <string>

#include <cmath>

#include <array>

#include <algorithm>

#include <queue>

#include <map>

using namespace std;



typedef  pair<int,int> P;

typedef long long LL;



const LL  INF=1<<31;







int main(){

     int n,k;

     cin>>n>>k;

     int h[100000];

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

          cin>>h[i];

     }

     LL dp[100001];



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

           dp[i]=INF;

      }

            dp[0]=0;

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







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

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

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



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

          }

     }     



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





}
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;



vector<int> dp(100005);



int main(){

    

    int n,k; 

    cin>>n>>k;

    

    vector<int> v (n);

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

        cin>>v[i];

    }

    

    dp[0] = 0;

    

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

        int x = INT_MAX;

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

            

            if(j<=i){

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

            x = dp[i];

            }

        }

        

    }

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

    

}




// Optimized solution to the same problem (faster):
/*Rabbi Zidni Ilma*/



#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define scl(n) scanf("%lld",&n)

#define scll(n,m) scanf("%lld%lld",&n,&m)

#define pb push_back

#define mp make_pair

#define fr first

#define sc second

#define mod 1000000007

#define read freopen("input.txt","r",stdin)

#define write freopen("output.txt","w",stdout)



ll dp[100005],ar[100005];



int main()

{

	ll n,k,i,j;

    scll(n,k);

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

    scl(ar[i]);

    

    dp[n]=0;

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

    {

    	dp[i]=INT_MAX;

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

    	{

    		if(i+j<=n)

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

    		else

    		break;

		}

	}

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

}




// Fastest known solution for this problem:
#include <iostream>

#include <array>

#include <vector>

#include <iomanip>

#include <string>

#include <cmath>

#include <array>

#include <algorithm>

#include <queue>

#include <map>

using namespace std;



typedef  pair<int,int> P;

typedef long long LL;



const LL  INF=1<<31;







int main(){

     int n,k;

     cin>>n>>k;

     int h[100000];

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

          cin>>h[i];

     }

     LL dp[100001];



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

           dp[i]=INF;

      }

            dp[0]=0;

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







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

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

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



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

          }

     }     



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





}
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define N (int)2e5

int n,k,memo[N],c[N];



int dp(int curr) {

    if (curr == n) return 0;

    if (curr > n) return 1e9;

    int &sol = memo[curr];

    if (sol != -1) return sol;

    int keep = INT_MAX;

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

        keep = min(

            dp(curr + i) + abs(c[curr] - c[curr + i]) ,

            keep

        );

    }

    return sol = keep;

}



int main() {

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

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

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

    memset (memo , -1 , sizeof memo);

    printf("%d\n" , dp(1));

}


// Optimized solution to the same problem (faster):
#include "bits/stdc++.h"



#define ll long long

#define ull unsigned long long

#define ld long double



#define tiii tuple < int, int, int >

#define pii pair < int, int >

#define pll pair < ll, ll >

#define pci pair < char, int >

#define psi pair < string, int >

#define pis pair < int, string >



#define vi vector < int >

#define vd vector < double >

#define vld vector < ld >

#define vll vector < ll >

#define vs vector < string >

#define vc vector < char >

#define vpi vector < pii >

#define vpll vector < pll >

#define vpis vector < pis >



#define pb push_back

#define mt make_tuple

#define gt0 get < 0 >

#define gt1 get < 1 >

#define gt2 get < 2 >



#define pi acos(-1)



#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)



using namespace std;



const int maxn = 1e5 + 5;

const int mod = 1e9 + 9;



ll a[maxn], f[maxn];



int main()

{

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

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



    fast;



    int n, k;



    cin >> n >> k;



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



    f[n] = 0;



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

        f[i] = 1e18;



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

            if(i + j > n) continue;



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

        }

    }



    cout << f[1] << endl;



    return 0;

}

// Fastest known solution for this problem:
#include <iostream>

#include <array>

#include <vector>

#include <iomanip>

#include <string>

#include <cmath>

#include <array>

#include <algorithm>

#include <queue>

#include <map>

using namespace std;



typedef  pair<int,int> P;

typedef long long LL;



const LL  INF=1<<31;







int main(){

     int n,k;

     cin>>n>>k;

     int h[100000];

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

          cin>>h[i];

     }

     LL dp[100001];



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

           dp[i]=INF;

      }

            dp[0]=0;

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







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

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

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



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

          }

     }     



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





}