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



using namespace std;



typedef long long int ll;

#define inf 0x3f3f3f3f

#define endl '\n'

// #define case(i) "Case #" << i << ": "



int n, k;

vector<int> v;

int dp[100001];



int solve(int i) {

    if(i == 0) return 0;

    else {

        int mn = inf;

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

            if(dp[i-j] == -1) dp[i-j] = solve(i-j);

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

        }

        return mn;

    }

}



int main() {

    ios_base::sync_with_stdio(false);

    cin.tie(0);



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



    cin >> n >> k;

    v.resize(n);



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



    cout << solve(n-1) << endl;

}

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



using namespace std;



typedef long long int ll;

#define inf 0x3f3f3f3f

#define endl '\n'

// #define case(i) "Case #" << i << ": "



int n, k;

vector<int> v;

int dp[100001];



int main() {

    ios_base::sync_with_stdio(false);

    cin.tie(0);



    cin >> n >> k;

    v.resize(n);



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



    dp[0] = 0;



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

        int mn = inf;

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

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

        }

        dp[i] = mn;

    }

    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;

const int MAXN = 20;

struct number

{

	int f,s;

}a[1<<MAXN];

int n;

int main()

{

	scanf("%d", &n);

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

	{	

		int x;

		scanf("%d", &x);

		a[i].f=x; 

	}

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

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

			if(i>>j & 1) 

			{

				int x=i^(1<<j); 

				number ans;

				ans.f=max(a[i].f,a[x].f); 

				if(a[i].f>a[x].f) 

					ans.s=max(a[i].s,a[x].f); 

				else

					ans.s=max(a[i].f,a[x].s);

				a[i]=ans;

			}

	int ans=0;

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

	{

		ans=max(ans,a[i].f+a[i].s); 

		cout<<ans<<endl;

	}

	cout<<endl;

	return 0;

}

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


#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define inf 20021225

#define ll long long

using namespace std;

int a[(1<<18)|1];

int mx[1<<18][2];

int ans[1<<18];

bool cmp(int x,int y){return a[x]<a[y];}

int main()

{

	int n;

	scanf("%d",&n);

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

	{

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

		mx[i][0] = i;

		mx[i][1] = (1<<n);

	}

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

	{

		int tmp[4]={0};

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

			if((i>>j)&1)

			{

				int _i = i^(1<<j);

				tmp[0] = mx[i][0]; tmp[1] = mx[i][1];

				tmp[2] = mx[_i][0]; tmp[3] = mx[_i][1];

				sort(tmp,tmp+4,cmp);

				mx[i][0] = tmp[3]; mx[i][1] = tmp[2]==tmp[3]?tmp[1]:tmp[2];

				//printf("%d %d\n",mx[i][0],mx[i][1]);

			}

		ans[i] = a[mx[i][0]] + a[mx[i][1]];

	}

	for(int i=1;i<(1<<n);i++)	ans[i] = max(ans[i],ans[i-1]);

	for(int i=1;i<(1<<n);i++)	printf("%d\n",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 <iostream>

#include <algorithm>

#include <string>

#include <cmath>

#include <cstring>

#include <iomanip>



using namespace std;

typedef long long ll;

const int maxn=1e5+1111;



int arr[maxn];

int dp[maxn];

int main(){

    int n,k;

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

    dp[0]=dp[1]=0;

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

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

        if(i>1) dp[i]=dp[i-1]+abs(arr[i]-arr[i-1]);

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

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

        }

    }

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

    return 0;

}

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

#include <cstring>



using namespace std;



const int maxn = 1e5+5;

int n,K;

int h[maxn],f[maxn];



int abs(int x,int y) {

	if (x - y < 0) return y - x;

	return x - y;

}



int min(int x,int y) {

	if (x < y) return x;

	return y;

}



int main() {

	memset(f,0x3f,sizeof(f));

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

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

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

	}

	f[0] = f[1] = 0;

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

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

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

		}

	}

	printf ("%d\n",f[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;

typedef long long ll;

const int inf=0x3f3f3f3f;

const int N=2e5+5;

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

int main(){

	cin>>n>>k;

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

		cin>>a[i];

	dp[1]=0;

    dp[0]=0;

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

    	dp[i]=inf;

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

      for(int j=i-1;j>=max(1,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<stdio.h>

#include<stdlib.h>

#include<math.h>





typedef long long ll;





ll *mem, *inp, dist, min_dist, N;

int k;



int main()

{

    ll i, j;

    scanf("%lld%d", &N, &k);



    mem =(ll*) malloc(N * sizeof(ll));

    inp =(ll*) malloc(N * sizeof(ll));



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

        scanf("%lld", inp+i);

    }



    *(mem+N-2) = llabs(*(inp+N-2) - *(inp+N-1));



    for(i = 3; i<=k+1 && i<=N; ++i)

        *(mem+N-i) = llabs(*(inp+N-i) - *(inp+N-1));



    for(i = N-(k+2); i>=0; --i){



        min_dist = llabs(*(inp+i) - *(inp+i+1)) + *(mem+i+1);

        for(j = 2; j<=k && i+j<N; ++j){

            dist = llabs(*(inp+i) - *(inp+i+j)) + *(mem+i+j);

            if (dist < min_dist) min_dist = dist;

        }



        *(mem+i) = min_dist;

    }



    printf("%lld\n", *mem);



    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> v(N, 0);

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



int cost(int pos, int n, int x){

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

    else if (pos == n) return 0;

    else {

        int min_cost = INT_MAX;

        int curr_cost = 0;

        for (int k=pos+1; k<=min(n, pos+x); k++){

            curr_cost = abs(v[pos] - v[k]) + cost(k, n, x);

            min_cost = min(curr_cost, min_cost);

        }

        memo[pos] = min_cost;

        return memo[pos];

    }

}



int main(){

    int n, x; cin >> n >> x;

    

    for (int i = 1; i!=n+1; i++) cin >> v[i];

    cout << cost(1, n, x) << endl;



    return 0;

}

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

#define eps 1e-3

#define pi acos(-1.0)

#define inf 0x3f

#define INF 0x3f3f3f3f

#define pb push_back

#define debug1 cout<<"&&";

#define debug2 cout<<"**";

#define ms(a, x) memset(a, x, sizeof(a))

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

#define for1(i, n) for(int i = 1; i <= n; ++i)

using namespace std;

typedef double db;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int, int> pii;

typedef pair<long long, int> pli;

typedef pair<long long, long long> pll;

const int mod = 1e9 + 7;

const int N = 1e5+10;

const int M = 1e6+10;

inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

inline ll Pow(ll a, ll b) { ll ans = 1; for( ; b; b >>= 1) { if(b&1) ans = ans * a % mod; a = a * a % mod;} return ans;}

inline ll Mul ( ll a, ll b)  { ll lf = a * ( b >> 25ll ) % mod * ( 1LL << 25 ) % mod; ll rg = a * ( b & ( ( 1ll << 25 ) - 1 ) ) % mod; return ( lf + rg ) % mod;}

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



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



int main() {

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

   for1(i, n) scanf("%d", h+i);

   ms(dp, inf); dp[n] = 0;

   for(int i = n; i; --i)

      for1(j, k) {

         if(i - j < 1) break;

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

      }

   printf("%d\n", dp[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<iostream>

#include<string>

using namespace std;



int main(){

    int k;

    string s;

    while(cin>>k){

        cin >> s;

        if(k<s.size()){

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

                cout << s[i];

            }

            cout << "..." << endl;

        }

        else

            cout << s << endl;

    }

    return 0;

}

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

#include<string.h>



int main()

{

	int n;

	scanf("%d",&n);

	char str[102];

	scanf("%s",&str);

	int len=strlen(str);

	if(len>n)

	{

		str[n]='.';

		str[n+1]='.';

		str[n+2]='.';

		str[n+3]='\0';

	}

	printf("%s",str);

	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<bits/stdc++.h>

using namespace std;



int main(){

	string s;

	cin>>s;

	string res=s;

	int p = 0;

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

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

			res[p++] = '0';

		}else if(s[i]=='1'){

			res[p++] = '1';

		}else{

			p += p>0?-1:0;

		}

	}

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

		cout<<res[i];

	}

	cout<<endl;

	return 0;

}

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

#include<stdlib.h>

#include<cstring>

int main()

{

	char s[100],ss[100];

	int i=0,j=0,a=0;

	int b[100];

	for(i = 0 ; i < 10 ; i++)b[i] = 1;

	scanf("%s",s);

	a = strlen(s);

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

	{

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

		{

			b[i]=0;

			for(j = i; j >=0 ;j--)

			{

				if(b[j]!=0)

				{

					b[j]=0;

					break;

				}

			}

		}

	}

	j = 0;

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

	{

		if(b[i]==1){

			ss[j]=s[i];

			j++;

		}

	}

	ss[j] = 0;

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

	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<iostream> 

#include<string>

using namespace std;

int main(){

	string s;

	int n;

	while(cin>>n){

		cin>>s;

		if(n<s.size()){

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

			cout<<s[i];	

		}

			cout<<"..."<<endl;

	}

		else	

			cout<<s<<endl;	

	}

	return 0;

}

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

#include<string.h>



int main()

{

	int n;

	scanf("%d",&n);

	char str[102];

	scanf("%s",&str);

	int len=strlen(str);

	if(len>n)

	{

		str[n]='.';

		str[n+1]='.';

		str[n+2]='.';

		str[n+3]='\0';

	}

	printf("%s",str);

	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):
#define _CRT_SECURE_NO_WARNINGS

#include <bits/stdc++.h>

#include <unordered_map>

#define stop(x) {cout<<x<<endl;exit(0);}

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

#define szz(s) int(s.size())

#define endl '\n'

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

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

typedef long long ll;

using namespace std;



void file() {

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

#ifndef ONLINE_JUDGE

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

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

#endif

}







int main() {

    //file();



    ll n, m;

    cin >> n >> m;

    vector < ll > v(n);



    for (auto& e : v)cin >> e;



    vector < ll > dp(n + 1, 1e11);



    dp[0] = 0;



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

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

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

        }

    }



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



        

}

// 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 <bits/stdc++.h>



using namespace std;



const int N = 200001;

int h[N], dp[N];

int n, k;



int solve(int pos) {

    if (pos == 1) {

        return 0;

    }

    int& ans = dp[pos];

    if (ans != -1) {

        return ans;

    }

    ans = 2e9;

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

        if (pos - i >= 1) {

            ans = min(ans, solve(pos - i) + abs(h[pos] - h[pos - i]));

        }

    }

    return ans;

}



int main() {

    cin >> n >> k;

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

        cin >> h[i];

    }

    memset(dp, -1, sizeof dp);

    cout << solve(n);

    return 0;

}


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



using namespace std;



const int N = 1e5 + 1;

int dp[N], h[N];



int main() {

    int n, k;

    cin >> n >> k;

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

        cin >> h[i];

    }

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

        dp[i] = 1e9;

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

            if (i - j >= 1) {

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

            }

        }

    }

    cout << 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 main() {

    int a[1000010]={};

    int s;

    cin >> s;

    a[s]++;

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

        if(s%2==0){

            if(a[s/2]==1){

                cout << i+1 << endl;

                return 0;

            }

            else{

                a[s/2]++;

                s /= 2;

            }

        }

        else{

            if(a[s*3+1]==1){

                cout << i+1 << endl;

                return 0;

            }

            else{

                a[s*3+1]++;

                s = 3*s +1;

            }

        }

    }

}




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

using namespace std;



int main() {

    int s;

    cin >> s;

    set<int> set1;

    set1.insert(s);

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

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

        else s = 3*s+1;

        set1.insert(s);

        if(set1.size()!=i+1){

            cout << i+1 << endl;

            return 0;

        }

    }

}




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



int main()

{

    int s;

    std::cin >> s;

    int list[1000000];

    int index = 0;

    int a_i;

    int a_pre = s;

    list[0] = s;

    index = index + 1;

    bool search_flag = false;

    while( true){

        if ( a_pre % 2 == 0){

            a_i = a_pre / 2;

        } else {

            a_i = 3 * a_pre + 1;

        }

        list[index] = a_i;

        index = index + 1;

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

            if ( list[i] == a_i) {

                search_flag = true;

                break;

            }

        }

        if (search_flag==true){

            break;

        } 

        a_pre = a_i;



    }

    std::cout << index << std::endl;

    return 0;

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

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

//deque/functional/iterator/list/map/memory/numeric/queue/set/stack/utility/vector

//#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int mod=1e9+7;



ll fact(ll n){

    if(n==0) return 1;

    else return (n*fact(n-1))%mod;

}



int main(){

    ios::sync_with_stdio(false);

    ll n;

    cin>>n;

    cout<<fact(n)<<endl;

    return 0;

}


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

const long long MOD=1e9+7;

int n;

long long ans=1;

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++) ans=(ans*i)%MOD;

	printf("%lld",ans);

}

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

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

using namespace std;

using ll = long long;

using P = pair<ll, ll>;

const string ln = "\n";

constexpr int INF = 1001001001;

constexpr int MOD = 1000000007;



int main() {

  cin.tie(nullptr);

  ios::sync_with_stdio(false);



  int n;

  cin >> n;



  ll ans = 1;



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

    ans *= i % MOD;

    ans %= MOD;

  }



  cout << ans << ln;



  return 0;

}