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



using namespace std;

 

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

 

#define nl '\n'

 

#define y1 aza_ibagaliev

 

#define f first

#define s second

	

#define ed end()

#define bg begin()

#define rbg rbegin()

 

#define rv reverse

#define mp make_pair

#define pb push_back

#define ppb pop_back

#define ppf pop_front

 

#define sz size()

#define all(x) x.bg, x.ed

 

#define pll pair < ll, ll >

#define pii pair < int, int >

 

#define sqr(x) ((x) * 1ll * (x))

#define sqrd(x) ((x) * 1.0 * (x))

 

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

 

#define rnl cout << "----------------------------------------" << nl

 

#define bit __builtin_popcount

 

inline ll bip(ll x, ll n, ll mod){ll res=1;while(n){if(n & 1){res=(res*x)%mod;}x=(x*x)%mod;n>>=1;}return res;}

        	

const int ppr = 257;

const ll INF = 2e18;

const int inf = 2e9;

const int mod = 1e9 + 7;

const int N = 1e6 + 123;        	

const ld pi = 3.1741592653589793238462643;

 

const int dx[] = {1, 0, -1, 0};

const int dy[] = {0, 1, 0, -1};



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



main() {             	

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

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



//	srand(time(NULL));



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



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

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



		if(i == 1) continue;



		dp[i] = INF;

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

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

	}



	cout << dp[n];

             

    return 0;                                        

}

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

}

// 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 <map>

using namespace std;

using ll = long long;



int main() {

	int N;

	cin >> N;

	map<int, ll> A;

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

		int a;

		cin >> a;

		auto it = A.find(a);

		if (it == A.end()) {

			A.emplace(a, 1);

		} else {

			(it->second)++;

		}

	}

	ll S = 0;

	for (auto p : A) {

		S += p.first * p.second;

	}

	int Q;

	cin >> Q;

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

		int B, C;

		cin >> B >> C;

		if (A.find(B) != A.end()) {

			S += (C - B) * A.at(B);

			if (A.find(C) == A.end()) {

				A.emplace(C, A.at(B));

			} else {

				A.at(C) += A.at(B);

			}

			A.erase(B);

		}

		cout << S << endl;

	}

	return 0;

}


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



int main() {

	int N;

	scanf("%d", &N);

	int A[100000 + 1] = {0};

	long long S = 0;

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

		int a;

	 	scanf("%d", &a);

		A[a]++;

		S += a;

	}



	int Q;

	scanf("%d", &Q);

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

		int B, C;

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

		printf("%lld\n", S += (C - B) * A[B]);

		A[C] += A[B];

		A[B] = 0;

	}

	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>

#define ll long long

using namespace std;



int dp[100005], a[100005];

int n,k;



int solve(int n, int k)

{

    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]));

        }

    }

    return dp[n-1];



}

int main()

{

    cin>>n>>k;

    memset(dp, 1000000, sizeof(dp));

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

        cin>>a[i];

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

}




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

using namespace std;

const int INF = 1e9 + 5;



int main() {

    int n, k;

    cin>>n>>k;

    vector<int> stone(n);

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

        cin >> stone[i];



    vector<int> dp(n, INF);

    dp[0] = 0;



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

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

            if(j<n)

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



    cout << dp[n - 1];

    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 arr[100100], dp[100100];



int main() {

  int n, k;

  cin >> n >> k;

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



  dp[0] = 0;

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



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

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

      if ( pos - step < 0 ) break;

      dp[pos] = min( dp[pos], dp[pos - step] + abs(arr[pos] - arr[pos - step]) );

    }

  }

  

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

  return 0;

}

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

} 

// 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 n,k,dp[100009],a[100009],mx=1e9+8;

int bt(int x)

{

    if(x==0)return 0;

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

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

    dp[x]=mx;

    for(int i=1;i<=k&&x-i>=0;i++)

    {

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

    }

    return dp[x];

}

int main()

{

    cin>>n>>k;

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

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

    cout<<bt(n-1);

}


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

using namespace std;

int n,k,dp[100009],a[100009],mx=1e9+8;

int main()

{

    cin>>n>>k;

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

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

    dp[0]=0;

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

    {

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

        {

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

        }

    }

    cout<<dp[n-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 ll long long

#define pb push_back

#define mp make_pair



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



int main()

{

    cin>>n>>k;

    for(ll i=0;i<100005;i++) dp[i] = LONG_LONG_MAX;

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

    dp[0] = 0;

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

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

    {

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

        {

            if(i-j>=0)

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

        }

    }

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

}

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

using namespace std;

#define ll long long

#define pb push_back

#define mp make_pair

#define ff first

#define ss second

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

#define repv(i,a,b) for(ll i=b-1;i>=a;i--)

#define MAXN 100005

#define endl "\n"



ll power(ll x,ll y){ll res=1; while(y>0){if(y&1) res=res*x;y=y>>1;x=x*x;}return res;}



int n,k,h[MAXN],dp[MAXN];



int main()

{

	ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    cin>>n>>k;

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

    rep(i,1,n+1) dp[i]=INT_MAX;

    dp[1]=0;

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

    {

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

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

    }

    cout<<dp[n]<<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 <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <map>

#include <cmath>

#include <queue>

#include <set>

#include <ctime>

#define rep(i,j,k) for(int i = j; i <= k; i++)

#define dow(i,j,k) for(int i = j; i >= k; i--)

#define ez(i,x) for(int i = h[x]; i; i = e[i].next)

#define fi first

#define se second

#define MS(x) memset(x, 0, sizeof(x))

using namespace std;





int main() {

    int n;

	ios::sync_with_stdio(0);

	cin >> n;

	map<int,int> m;

	long long sum = 0;

	rep(i,1,n) {

		int x;

		cin >> x;

		m[x]++;

		sum += x;

	}

	int q;

	cin >> q;

	while (q--) {

		int x, y;

		cin >> x >> y;

		sum = sum - 1ll * m[x] * x + m[x] * 1ll * y;

		m[y] += m[x];

		m[x] = 0;

		cout << sum << "\n";

	}

}

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

#include<algorithm>

#include<cstring>



using namespace std;



int num[100100];



int main()

{

    int n,k,i;

    int a,b,q;

    long long t;

    long long total=0;

    scanf("%d",&n);

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

    {

        scanf("%d",&a);

        total+=a;

        num[a]++;

    }

    scanf("%d",&q);

    while(q--)

    {

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

        t=num[a];

        num[a]=0;

        num[b]+=t;

        total+=t*b-t*a;

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

    }

    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>



#include <iostream>

#define pb push_back

#define sort_incr(v) sort(v.begin(),v.end());

#define sort_decr(v) {sort(v.begin(),v.end()); reverse(v.begin(),v.end());}

#define take_input(v,n) for(ll i=0,temp;i<n;i++){cin>>temp;v.pb(temp);}

#define fastio {ios_base::sync_with_stdio(false);    cin.tie(NULL);}

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



typedef long long ll;

using namespace std; 



int main() 

{

    fastio;

    ll n,temp,su=0;

    cin>>n;

    vector<ll> v;

    int co[100004]={0};

    // take_input(v,n);

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

    {

        cin>>temp;

        co[temp]++;

        su=su+temp;

    }

    ll q ;

    cin>>q;

    while(q--)

    {

        ll a,b;

        cin>>a>>b;

        su=su+(b-a)*co[a];

        co[b]+=co[a];

        co[a]=0;

        

        cout<<su<<"\n";

        

    }

    

    return 0; 

} 

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


#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <map>

#include <cmath>

#include <queue>

#include <set>

#include <ctime>

#define rep(i,j,k) for(int i = j; i <= k; i++)

#define dow(i,j,k) for(int i = j; i >= k; i--)

#define ez(i,x) for(int i = h[x]; i; i = e[i].next)

#define fi first

#define se second

#define MS(x) memset(x, 0, sizeof(x))

using namespace std;





int main() {

    int n;

	ios::sync_with_stdio(0);

	cin >> n;

	map<int,int> m;

	long long sum = 0;

	rep(i,1,n) {

		int x;

		cin >> x;

		m[x]++;

		sum += x;

	}

	int q;

	cin >> q;

	while (q--) {

		int x, y;

		cin >> x >> y;

		sum = sum - 1ll * m[x] * x + m[x] * 1ll * y;

		m[y] += m[x];

		m[x] = 0;

		cout << sum << "\n";

	}

}

// 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;

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 = 1;i < n;i++){

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

			if(i + j <= n)

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

		}

	}

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

	return 0;

}

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

     **author : _KMS_

     **created : 28-03-2020

**/

#include<bits/stdc++.h>

using namespace std;

const long long M =2e5+10,MOD=998244353;

typedef long long ll;

int arr[M];

int dp[M];

int main() {

   

  ios::sync_with_stdio(false);

  cin.tie(0);

  int n,k;

  cin>>n>>k;

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

  cin>>arr[i];

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

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

 arr[0]=arr[1];

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

  {  int temp=k;

     int in=i-1;

     while(temp>0&&in>0){

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

    temp--;

    in--;

  }

  }

  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;



#define INF 1e9



typedef vector <int> vi;



int main() {

    int n, k;

    cin >> n >> k;



    int v[n];

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



    vi dp(n, INF);

	dp[0] = 0;



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

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

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

		}

    }



	// for (int i = 0; i < n; i++) cout << dp[i] << " ";

	// cout << endl;



    cout << dp[n-1] << 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<bits/stdc++.h>

#define fr(i,a,n) for(ll i=a;i<n;i++)

#define YES cout<<"YES"<<endl

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

#define NO cout<<"NO"<<endl

#define pb(x) emplace_back(x)

#define fastio std::ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define vi vector<ll>

#define mi map<ll,ll>

#define pi pair<ll,ll>

#define what(x) cout<<#x<<" ="<<x<<endl;

#define scn(n) scanf("%d",&n)

#define print(a) printf("%d",a);

using namespace std;

using ll =int;

ll n;



ll dp[200005],a[200005]={1000000000};

ll invalid=1e9,k;

ll cnt=0;

int solve(ll i,ll p)

{ //cnt++;

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

    if(i>=n)return 1e9;

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

    //what(p-a[i]);

    //cout<<i<<" GG "<<i+1<<endl;

    ll ans=1e9,x;

    fr(l,1,min(k,n)+1){

        //what(l);

    x=abs(a[i+l]-a[i])+solve( i+l,a[i]);



    ans=min(x,ans);



    }







    return dp[i]=ans;



}



int main()

{

    ll t;

    memset(dp,-1,sizeof dp);



    scn(n);

    scn(k);

    fr(i,0,n)cin>>a[i];



    solve(0,a[0]);



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

    //what(cnt);

    //fr(i,0,n)cout<<dp[i]<<" ";



}




















































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

typedef long long ll;

using namespace std;

ll dp[100005];

int main()

{

   ll n,k;

   cin>>n>>k;

   ll a[n];

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

    cin>>a[i];

    dp[i]=1000000000;

   }

   dp[n-1]=0;

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

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

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

   }

   }

   cout<<dp[0];

    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;





}