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

using namespace std;

const int N=1<<19;

int n,s,a[N];

int id[N][2];

bool cmp(int A,int B){

    return a[A]<a[B];

}

int main(){

    scanf("%d",&n);

    s=1<<n;

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

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

    a[s]=-1;

    id[0][0]=0,id[0][1]=s;

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

        id[i][0]=i,id[i][1]=s;

        int x[4];

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

            if (i&(1<<j)){

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

                x[0]=id[i][0],x[1]=id[i][1];

                x[2]=id[_i][0],x[3]=id[_i][1];

                sort(x,x+4,cmp);

                id[i][0]=x[3],id[i][1]=x[2]==x[3]?x[1]:x[2];

            }

    }

    int mx=0;

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

        mx=max(mx,a[id[i][0]]+a[id[i][1]]);

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

    }

    return 0;

}

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

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<queue>

#include<vector>

#include<ctime>

#include<map>

#include<bitset>

#include<set>

#define LL long long

#define mp(x,y) make_pair(x,y)

#define pll pair<long long,long long>

#define pii pair<int,int>

using namespace std;

inline int read()

{

	int f=1,x=0;char ch=getchar();

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

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

	return x*f;

}

int stack[20];

inline void write(LL x)

{

	if(x<0){putchar('-');x=-x;}

    if(!x){putchar('0');return;}

    int top=0;

    while(x)stack[++top]=x%10,x/=10;

    while(top)putchar(stack[top--]+'0');

}

inline void pr1(int x){write(x);putchar(' ');}

inline void pr2(LL x){write(x);putchar('\n');}



const int MAX_N=20;

int bin[MAX_N];

#define pr pair<int,int>

#define FR first

#define SE second

#define MP make_pair

int a[1<<MAX_N];pr b[1<<MAX_N];

int gmax(int x,int y){return a[x]>a[y]?x:y;}

pr merge(pr x,pr y)

{

	if(a[x.FR]>a[y.FR]) return MP(x.FR,gmax(x.SE,y.FR));

	else return MP(y.FR,gmax(x.FR,y.SE));

}

void fwt(int n)

{

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

		for(int j=bin[n]-1;j>=0;j--) if(j&bin[i])

				b[j]=merge(b[j],b[j^bin[i]]);

}

int main()

{

	bin[0]=1;for(int i=1;i<MAX_N;i++) bin[i]=bin[i-1]<<1;

	

	int n;scanf("%d",&n);a[bin[n]]=0;

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

	fwt(n);

	int lst=0;

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

	{

		lst=max(a[b[i].FR]+a[b[i].SE],lst);

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

	}

}

/*

4

75 26 45 72 81 47 97 97 2 2 25 82 84 17 56 32

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

using namespace std;



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

#define rall(x) (x).begin(),(x).rend()



typedef vector<int> vi;

typedef long long ll;

typedef pair<int,int> PII;

typedef pair<long long,long long> PLL;



const int inf=1e9;

const int mod=1e9+7;



vi dp(100110,inf);



int main(){

	int n,k;

	cin>>n>>k;

	int h[n];

	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){

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

		}

	}



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





	return 0;

}

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

using namespace std;



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

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

#define pb push_back



template<class T>bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}

template<class T>bool chmin(T &a,T b){if(a>b){a=b;return 1;}return 0;}



typedef long long ll;

typedef pair<int,int> pii;

typedef vector<int> vi;

typedef vector<vi> vvi;



const int inf=1e9;

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

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



int main(){

	int n,k;

	cin>>n>>k;

	vi h(n);

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

		cin>>h[i];

	}



	vi dp(n,1e+9);

	dp[0]=0;

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

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

			if(i+j>=n)continue;

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

		}

	}



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



	return 0;

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

using namespace std;

int main()

{

    int a,b,c;

    cin>>a>>b;

    c=b-a+1;

    int i;

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

    {

        cout<<c<<" ";

        c++;

    }

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

    {

        cout<<c<<" ";

        c++;

    }

    return 0;

}


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

#include<stdio.h>

int main(){



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

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

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

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

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

if(k==1)

{

    printf("%d",x);

}

else{

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

    {

        printf("%d ",i);

    }

    printf("%d",r);

}



return 0;

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

#include<iostream>

#include<deque>

using namespace std;

int main()

{

    string s;

    deque<int>ans;

    cin>>s;

    int len = s.size();

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

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

            ans.push_back(0);

        }

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

            ans.push_back(1);

        }

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

            if(ans.size()!=0)ans.pop_back();

        }

    }

    while(!ans.empty()){

        printf("%d", ans.front());

        ans.pop_front();

    }



    return 0;

}


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

#include<string.h>



int main(){

	char str[15];

	scanf("%s",&str);

	char temp[15];

	int index=0,len=strlen(str);

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

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

			temp[index] = '0';

			//printf("index[%d] : %s\n",index,temp);

			index++;

		} 

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

			temp[index] = '1';

			//printf("index[%d] : %s\n",index,temp);

			index++;

		} 				//01B0 temp =     --0

		else if(str[i]=='B'){

			//printf("index[%d] : %s\n",index,temp);

			if(index != 0) index--;

		}

	}

	//printf("%d\n",index);

	temp[index]='\0';

	printf("%s\n",&temp);

	

	

	

	return 0;

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

using namespace std;

//*******************

// Mahmoud Magdy    *

//*******************

#define ll long long

#define endl "\n"



void fast()

{

    ios_base :: sync_with_stdio( 0 ) ;

    cin.tie( 0 ) ;

    cout.tie( 0 ) ;

}

inline int D()

{

    int m ;

    cin>>m;

    return m ;

}

inline ll lD()

{

    ll m ;

    cin>>m;

    return m ;

}

inline double dD()

{

    double m ;

    cin>>m;

    return m ;

}

int main()

{

  fast();

  int n=D();

  int x=n/15;

  ll sum=1;

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

    sum=(sum*i)%1000000007;

  cout<<sum%1000000007<<endl;

}




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

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



#define filein freopen ("in.txt", "r", stdin)

#define fileout freopen ("out.txt", "w", stdout)

#define dbg(x) cerr << #x << ": " << x << endl



using namespace std;

typedef long long ll;



const int maxn = 100005;

const ll inf = 1e10;



ll a[maxn];

ll dp[maxn];



int main(){

	ll n, k;

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

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

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

	dp[1] = 0;

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

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

		dp[i] = inf;

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

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

		}

	}

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

	return 0;

}

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

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

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

//比如从k上面跳过来

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

//关键是你k不知道啊

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

//枚举

//dp[1] = 0

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

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

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

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

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

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <math.h>

#include <queue>

#include <stack>

#include <vector>

#include <algorithm>



using namespace std;



const int MAXN = 1e5;

int n,k;

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



int CHANGE(int i,int k)//

{

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

	{//从一开始选

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

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

		{

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

			{

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

			}

		}

		return min;

	}

	else

	{

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

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

		{

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

			{

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

			}

		}

		return min;

	}

}



int main()

{

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

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

	{

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

	}

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

	{

		if(i == 1)

		{

			dp[i] = 0;

		}

		else if(i == 2)

		{

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

		}

		else

		{

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

		}

	}

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

	return 0;

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

#define ll long long

#define PI 3.141592653589

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

#define EPS 1e-9

#define f first

#define s second

using namespace std;

int n, k;

int arr[100005];

ll memo[100005];

ll solve(int idx){

    if (idx >= n-1)

        return 0;

    ll &res = memo[idx];

    if(res != -1)

        return res;

    res = 1e18;

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

        res = min(res, abs(arr[idx+i]-arr[idx])+solve(idx+i));

    return res;

}

int main(){

    IO;

    cin >> n >> k;

    memset(memo, -1, sizeof memo);

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

        cin >> arr[i];

    cout << solve(0);



    return 0;

}


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

#define ll long long

#define PI 3.141592653589

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

#define EPS 1e-7

#define f first

#define s second

using namespace std;

int main() {

    IO;

    int n, k;

    cin >> n >> k;

    int arr[n+1];

    ll dp[n+1];

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

        cin >> arr[i];

    dp[1] = 0;

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

        dp[i] = 1e9;

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

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

        }

    }

    cout << dp[n];

    return 0;

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

using namespace std;

typedef long long int lli;

typedef vector <int> vi;

typedef vector <vi> vvi;

typedef pair <int,int> pr;

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

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

#define pb push_back

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

#define tr(c, i) for (typeof ((c).begin() i = (c).begin(); i != (c).end(); i++)

#define present(c, x)((c).find(x) != (c).end())

#define cpresent(c, x)(find(all(c), x) != (c).end())

// for mod power a^b%m use power<lli> (a,b,m)

template < class mytype >

mytype power(mytype a, mytype b, mytype m){if (b == 1) return a % m;if (b == 0) return 1;

lli root = power < lli > (a, b / 2, m);lli ans = (root * root) % m;if (b % 2) ans = (ans * a) % m;

return ans;

}

// for gcd use gcd<int> (a,b)

template < class type >type gcd(type a, type b){if (a == 0) return b;else return gcd(b % a, a);}

template < class type >type mod_inv(type a, type p) {return power(a, p - 2, p);}



// use from here bitches

int n, k;

vector<int> height(100002) , values(100002 , -1);

int dp(int x){

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

if(x >= n-1) return 0;int ans = INT_MAX;

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

	ans = min(ans , abs(height[x+j] - height[x]) + dp(x+j));

}

return values[x] = ans;

}





int main()

{    

	ios_base::sync_with_stdio(false);

	cin.tie(NULL);

	cin >> n >> k;

	fr(i , n){

		cin >> height[i];

	}

	cout << dp(0);

		



	





    return 0;

	

}


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

using namespace std;

typedef long long int lli;

typedef vector <int> vi;

typedef vector <vi> vvi;

typedef pair <int,int> pr;

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

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

#define pb push_back

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

#define tr(c, i) for (typeof ((c).begin() i = (c).begin(); i != (c).end(); i++)

#define present(c, x)((c).find(x) != (c).end())

#define cpresent(c, x)(find(all(c), x) != (c).end())

// for mod power a^b%m use power<lli> (a,b,m)

template < class mytype >

mytype power(mytype a, mytype b, mytype m){if (b == 1) return a % m;if (b == 0) return 1;

mytype root = power < lli > (a, b / 2, m);mytype ans = (root * root) % m;if (b % 2) ans = (ans * a) % m;

return ans;

}

// for gcd use gcd<int> (a,b)

template < class type >type gcd(type a, type b){if (a == 0) return b;else return gcd(b % a, a);}

template < class type >type mod_inv(type a, type p) {return power(a, p - 2, p);}





int main()

{

    int n , k;

    cin >> n >> k;

    vector<int> h(n) , cost(n , 1e9+7);

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

    cost[0] = 0;

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

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

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

        }

    }

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

    return 0;

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

#include<cstring>

#include<algorithm>

using namespace std;



namespace mine

{

    const int MAXN=110000;



    int n;



    int tr[2*MAXN];

    int lowbit(int x) {return x&-x;}

    void change(int d)

    {

        d+=MAXN;

        while(d<2*MAXN) tr[d]++,d+=lowbit(d);

    }

    int sum(int d)

    {

        d+=MAXN;

        int ans=0;

        while(d>=1) ans+=tr[d],d-=lowbit(d);

        return ans;

    }



    int a[MAXN],b[MAXN];

    int c[MAXN];



    typedef long long ll;//debug 爆int 

    bool check(int now)

    {

        for(int i=1;i<=n;i++) c[i]=c[i-1]+(a[i]<=now?1:-1);//1小于等于,-1大于



        memset(tr,0,sizeof tr);//debug

        change(c[0]);//debug 



        ll tot=0;//<=now的数，产生的贡献 

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

        {

            //c[r]-c[l-1]>0 => c[l-1]<c[r] (l-1<r)

            tot+=sum(c[r]-1);

            change(c[r]);

        }

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

    }

    void main()

    {

        scanf("%d",&n);

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



        int l=1,r=1e9,ans=-1;

        while(l<=r)

        {

            int mid=(l+r)/2;

            if(check(mid)) ans=mid,r=mid-1;

            else l=mid+1;

        }

        printf("%d",ans);

    }

};



int main()

{

    mine::main();

}

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

#include<algorithm>

using namespace std;

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

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

int n,a[110000],l,r,mi,f[220000];

long long m;

inline void add(int x){

	while (x<=n+n){

		f[x]++;

		x+=x&(-x);

	}

}

inline long long ask(int x){

	long long ans=0;

	while (x){

		ans+=f[x];

		x-=x&(-x);

	}

	return ans;

}

inline bool che(int x){

	int s=n+1;long long ans=0;//s=n TLE

	fo(i,0,n+n) f[i]=0;

	add(s);

	fo(i,1,n){

		if (a[i]>=x) s++;else s--;

		ans+=ask(s);

		add(s);

	}

	return ans>=m;

}

int main(){

	scanf("%d",&n);

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

	m=n*1ll*(n+1)/2;

	m=(m+1)/2;

	l=0x7fffffff;r=0;

	fo(i,1,n){

		if (a[i]<l) l=a[i];

		if (a[i]>r) r=a[i];

	}

	l--;r++;

	while (l+3<r){

		mi=(l+r)>>1;

		if (che(mi)) l=mi+1;else r=mi-1;

	}

	fd(i,r+1,l-1) if (che(i)){//che(mi)!!!

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

		return 0;

	}

	return 0;

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

#include <iostream>

#include <algorithm>



using namespace std;



vector<vector<int> > G;



vector<bool> used;



int rec(int pos)

{

    used[pos] = true; int ret = 1;

    

    for(int i = 0; i < G[pos].size(); i++)

    {

        if(!used[G[pos][i]])

        {

            ret = max(ret, rec(G[pos][i]) + 1);

        }

    }

    

    used[pos] = false;

    

    return ret;

}



int main()

{

    int N, A, B;

    

    while(true)

    {

        scanf("%d", &N);

        

        if(N == 0) { break; }



        G = vector<vector<int> >(100, vector<int>());

        

        used = vector<bool>(100);

    

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

        {

            scanf("%d", &A); A--;

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

        

            G[A].push_back(B);

            G[B].push_back(A);

        }

    

        int ret = 0;

    

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

        {

            if(G[i].size())

            {

                ret = max(ret, rec(i));

            }

        }

        

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

    }

    

    return 0;

}

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

#include <algorithm>

#pragma warning(disable : 4996)

using namespace std;

int N, A, B, v[100], r[100], G[100][199];

int rec(int pos) {

	int ret = 0; v[pos] = 1;

	for (int i = 0; i < r[pos]; i++) {

		if (!v[G[pos][i]]) ret = max(ret, rec(G[pos][i]));

	}

	v[pos] = 0;

	return ret + 1;

}

int main() {

	while (scanf("%d", &N), N) {

		for (int i = 0; i < 100; i++) r[i] = 0;

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

			scanf("%d%d", &A, &B), A--, B--;

			G[A][r[A]++] = B, G[B][r[B]++] = A;

		}

		int ret = 0;

		for (int i = 0; i < 100; i++) ret = max(ret, rec(i));

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

	}

	return 0;

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

using namespace std;

using ll = long long;

using vi = vector<int>;

using vc = vector<char>;

using vb = vector<bool>;

using vd = vector<double>;

using vs = vector<string>;

using vll = vector<long long>;

using vpii = vector<pair<int, int>>;

using vvi = vector<vector<int>>;

using vvc = vector<vector<char>>;

using vvs = vector<vector<string>>;

using vvb = vector<vector<bool>>;

using pii = pair<int, int>;

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

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

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

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

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

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

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

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

#define call(x) (x).cbegin(), (x).cend()

#define MAX(x) *max_element(all(x))

#define MIN(x) *min_element(all(x))

template<class T> inline bool chmax(T &a, T b) {if (a<b) {a=b; return 1;} return 0;}

template<class T> inline bool chmin(T &a, T b) {if (b<a) {a=b; return 1;} return 0;}

const int INF = INT_MAX;

const int MOD = 1000000007;

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

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



int main() {

    int N, K;

    cin >> N >> K;

    vi h(N);

    rep(i, N) cin >> h[i];



    vll dp(100500, INF);

    dp[0] = 0;

    FOR(i, 0, N-2) {

        reps(j, K) {

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

        }

    }

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

}

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

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

#define fi first

#define se second

#define pb push_back

#define eb emplace_back

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

using namespace std;

using ll = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vc = vector<char>;

using vb = vector<bool>;

using vs = vector<string>;

using vll = vector<long long>;

using vp = vector<pair<int, int>>;

using vvi = vector<vector<int>>;

using vvc = vector<vector<char>>;

using vvll = vector<vector<long long>>;

template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}

template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}



const int INF = 1001001001;



int main() {

    ios::sync_with_stdio(false);

    cin.tie(0);

    

    int n, k;

    cin >> n >> k;

    vi h(n);

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



    vi dp(n+k, INF);

    dp[0] = 0;

    rep(i, n) {

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

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

        }

    }

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

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

using namespace std;

#define    sz    100110

#define    ll    long long int

ll n,c=0,p,q,k;

ll num[sz];

ll vis[sz];

ll dp[sz];





ll tani(ll pos)

{

    ll mn=100000000000;



    if(pos>=n )

        return 0;

    if(vis[pos]==1)

        return dp[pos];



    vis[pos]=1;



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

    {

        mn=min(mn,abs(num[pos]-num[pos+i])+tani(pos+i));

    }

    // cout<<mn<<endl;

    return dp[pos]=mn;

}



int main()

{

    ll t,i;



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

        num[i]=10000000000;



    //cin>>n>>k;

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



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

    {

        // cin>>num[i];

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

    }

    t=tani(1);

    // cout<<t<<endl;

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

    return 0;

}




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

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long LL;

const int maxn = 1000010;

const int inf = 0x3f3f3f3f;

LL n;

LL dp[maxn];

LL a[maxn];

LL k;

inline LL max(LL x, LL y) {

	return x > y ? x : y;

}

inline LL min(LL x, LL y) {

	return x < y ? x : y;

}

int main(){

	ios::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

	cin >> n >> k;

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

		cin >> a[i];

	dp[0]=dp[1] = 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(1LL, i - k); j--)

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

	cout << dp[n];

	return 0;

}