stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<iostream>

using namespace std;



#define MAX 100000



void swap(int& a, int& b)

{

    int c;

    c = a; a = b; b = c;

}



int partition(int* A, int p, int r)

{

    int i, j, x;

    x = A[r];

    i = p - 1;

    for(j = p; j < r; j++){

        if(A[j] <= x){ i++; swap(A[i], A[j]); }

    }

    swap(A[i + 1], A[r]);



    return i + 1;

}



int main()

{

    int i, n, A[MAX], q;

    cin >> n;

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



    q = partition(A, 0, n - 1);



    for(i = 0; i < q; i++){ cout << A[i] << " "; }



    cout << "[" << A[q] << "]";



    for(i = q + 1; i < n; i++){ cout << " " << A[i]; }



    cout << endl;



    return 0;

}

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



#define MAX 100000



void swap(int& a, int& b)

{

    int c;

    c = a; a = b; b = c;

}



int partition(int* A, int p, int r)

{

    int i, j, x;

    x = A[r];

    i = p - 1;

    for(j = p; j < r; j++){

        if(A[j] <= x){ i++; swap(A[i], A[j]); }

    }

    swap(A[i + 1], A[r]);



    return i + 1;

}



int main()

{

    int i, n, A[MAX], q;

    scanf("%d", &n);

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



    q = partition(A, 0, n - 1);



    for(i = 0; i < q; i++){ printf("%d ", A[i]); }



    printf("[%d]", A[q]);



    for(i = q + 1; i < n; i++){ printf(" %d", A[i]); }



    printf("\n");



    return 0;

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

using namespace std;

#define int long long int



int n; //number of stones

int k; //farthest the frog can jump

vector<int> h; //height of the stones

vector<int> dp; //memorize heck



main(){

	cin >> n >> k;



	dp.assign(n, INT_MAX);

	

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

		int x;

		cin >> x;

		h.push_back(x);

	}



	dp[0] = 0;

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

		for(int 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-1] << "\n";

	

}

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

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

using namespace std;

main()

{

   int i,j,k,l;

    while(cin>>l){

  int x[200000]={0};

    i=0;

    while(1){ i++;

       x[l]++;

       if(x[l]==2) {  break;}

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

       else l=((3*l)+1);

    }

    cout<<i<<endl;

    } return 0;



}


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

using namespace std;



int main()

{

    map<int,int> mp,mp1;

    int n,c=1;

    cin>>n;

    mp[n]++;

    while(1)

    {

        if(n%2==0){

            n/=2;

            mp[n]++;

            if(mp[n]==2)break;

        }

        else{

            n=n*3 + 1;

            mp[n]++;

            if(mp[n]==2)break;

        }

        c++;

    }

    cout<<c+1<<endl;



    return 0;

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



using namespace std;







int main(){



    int n, k;

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

    int num = 0;

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

        int x;

        scanf("%d", &x);

        num += x >= k;

    }

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

}

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



int main()

{

    int n,k,ans=0;

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

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

    {

        int x;

        scanf("%d",&x);

        if(x>=k)ans++;

    }

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

    return 0;

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

#include<cstring>

using namespace std;



int main()

{long long n,q,k;

 string s;

 while(cin>>k>>s)

 {if(s.size()<=k)

  cout<<s<<endl;

  else

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

 }

return 0;

} 

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

	# include <string.h>

	int main () {

		int a = 0;

		int c =0;

	char name [100];

		scanf ("%d",&a);

		scanf("%s%[^\n]",&name);

		c = strlen (name);

		if (c<=a) {

			printf ("%s",name);

		} else if (c>a) {

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

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

			}

			printf("...");

		}

		return 0;

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

#include<cstring>

using namespace std;

int main()

{

	string s;

	int n;

	cin>>n>>s;

	int k=s.size();

	if(k<=n)

	cout<<s;

	else

	{

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

		{

			cout<<s[i];

		}

		cout<<"...";

	}

	return 0;

}

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

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

#define maxn (int)(2e5)

#define INF 1<<30

#define i64 long long

#define pii pair<i64,i64>

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

#define LB(x,v) lower_bound(all(x), v) - x.begin()

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

using namespace std;



int h[maxn+2], dp[maxn+2], n, k;



void init(int n){

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

}



int solve(int cur){

    if(cur >= n) return INF;

    if(cur == n-1) return 0;



    if(dp[cur] != INF) return dp[cur];



    //int res = INF;

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

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

    }



    return dp[cur];

}

int main() {

    /*BEFORE SUBMIT, CHECK

    sample i/o format

    statements for debugging are removed/comment out

    global values / stl containers are initialized/cleared for each test (if needed)

    all array size are sufficient

    loop variable or output value doesn't cross min/max limit of input

    // */

    // #ifndef ONLINE_JUDGE

    //     fread();

    // #endif

    

    while(scanf("%d %d",&n, &k)==2){

        init(n);

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

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

        }

        printf("%d\n", solve(0));

    }    

    return 0;

}

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

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

#include <iostream>

#include <algorithm>



using namespace std;



int N, A, B, used[100], rings[100], G[100][199];



int rec(int pos)

{

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



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

	{

		int r = G[pos][i];

		

		if(!used[r])

		{

			ret = max(ret, rec(r) + 1);

		}

	}



	used[pos] = 0;



	return ret;

}



int main()

{

	int N, A, B;



	while(true)

	{

		scanf("%d", &N);

 

		if(N == 0) { break; }



		memset(used, 0, sizeof(used));

		memset(rings, 0, sizeof(rings));



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

		{

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

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



			G[A][rings[A]] = B; rings[A]++;

			G[B][rings[B]] = A; rings[B]++;

		}



		int nodes = 0;



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

		{

			if(rings[i])

			{

				nodes++;

			}

		}



		int ret = 0;



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

		{

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



 			if(ret == nodes) break;

		}

 

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

	}



	return 0;

}

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

#define _GLIBCXX_DEBUG

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

#define ll long long

#define P pair<ll,ll>

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



const ll mod = 1e9+7;

const ll INF = 1e18;

const double pi = acos(-1.0);



int main(void)

{

    ll n, m, l=0, r=INF;

    cin >> n >> m;

    vector<ll> a(200000,0);

    rep(i,m){

        ll a, b;

        cin >> a >> b;

        l = max(l, a);

        r = min(r, b);

    }

    cout << max(0LL, r-l+1) << endl;

    return 0;

}

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

using namespace std;

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



int main(void)

{

    int n, m, l=1, r;

    cin >> n >> m;

  	r = n;

    rep(i,m){

        int a, b;

        cin >> a >> b;

        l = max(l, a);

        r = min(r, b);

    }

    cout << max(0, r-l+1) << endl;

    return 0;

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

using namespace std;

int n;

int k;

vector <int> v(100005);

int dp[100005];

int solve(int i){

    if(i==n){

        return 0;

    }

    if(i>n){

        return 2e9;

    }

    if(dp[i]!=-1){

        return dp[i];

    }

    int q =2e9;

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

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

    }

    dp[i]=q;

    return q;

}

void initialize(){

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

        dp[i]=-1;

    }

}

int main(){

    initialize();

    cin>>n;

    cin>>k;

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

        cin>>v[i];

    }

    cout<<solve(1)<<endl;

}


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

using namespace std;

vector <int> dp;

int solve(vector <int> & v, int index, int k){

	if(index>= (v.size()-1)){

		return 0;

	}

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

	int q = INT_MAX;

	for(int i=index+1; i<=index+k && i<v.size() ;i++){

		q = min(q, abs(v[i]-v[index])+solve(v, i , k));

	}

	dp[index] = q;

	return q;

}

int main(){

	int n;

  	cin>>n;

  	int k;

  	cin>>k;

  	vector <int> v(n);

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

    	dp.push_back(-1);

    	cin>>v[i];

	}

	cout<<solve(v, 0, k);

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

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<string>

#include<iostream>

#include<algorithm>

#include<map>

using namespace std;

int a,b,c;

int main(){

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

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

		if(((i*b)+c)%a==0){

			printf("YES\n");

			return 0;

		}

	}

	printf("NO\n");

}

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

#include<cstdlib>

#include<cstring>

#include<string>

#include<algorithm>

using namespace std;



int main()

{

	int a, b, c, d, flag = 0;

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

	d = a;

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

	{

		if(d % b == c)

		{

			flag = 1;

			break;

		}

		else

	        d += a;

	}

	if(flag == 1)

		printf("YES\n");

	if(flag == 0)

        printf("NO\n");

    return 0;

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

#include <limits.h>

#include <algorithm>  

#include <numeric>

 

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

using namespace std;

 

#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define endl '\n'

using ll = long long;

 

const int precision = 3;

const int modulo =  1000000007; // 10^9 + 7

const ll lmodulo =  1000000007; // 10^9 + 7

 

const double EPS = 1e-9;

const ll inf = 1e18;

 



void solve() {

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

	vector<int> h(n);

	for (auto &it : h) cin >> it;



	vector<int> dp(n, 1e9 + 100);

	dp[0] = 0;



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

		for (int j = i - 1; j >= i - k and j >= 0; --j) {

			int a = abs(h[i] - h[j]);

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

		}

	}



	cout << dp[n - 1];

}



int main() {

  ios_base::sync_with_stdio(false);

  cin.tie(nullptr);

  cout.tie(nullptr);

  cout.precision(precision);

  cout.setf(ios_base::fixed);

  solve();

  return 0;

}




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

#include<cmath>

#include<algorithm>

using namespace std;

const int maxn=1e5 + 5;

int main()

{

	int dp[maxn];

	int h[maxn];

	int n,k;

	while(~scanf("%d %d",&n,&k)){

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

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

		dp[1] = 0;

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

	    	dp[i]=1e9;

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

				if(i==j) break;

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

				}

	}

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

	}

	return 0;

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

using namespace std;

#define ll long long

#define pb push_back

#define F first

#define S second

const int mod = 1e9+7, A = 1e5+5;

ll n, k, h[A], dp[A];

ll table1()

{

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

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

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

	return dp[n-1];

}

ll table2()

{

	dp[0] = 0;

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

	{

		dp[i] = 1e9;

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

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

	}

	return dp[n-1];

}

int main()

{

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

	cin >> n;

	cin >> k;

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

	//cout << table1();

	cout << table2();

	return 0;

}


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

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

#include <map>

#include <queue>

#include <cmath>

#include <vector>

#include <string>

#include <algorithm>

#include <functional>

using namespace std;



int N, M, P[1 << 18]; string S[1 << 18];

int flag[1 << 18], penalty[1 << 18];



int main() {

	cin >> N >> M;

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

		cin >> P[i] >> S[i];

		if (S[i] == "AC") flag[P[i]] = 1;

		else if (flag[P[i]] == 0) penalty[P[i]]++;

	}

	int sum1 = 0, sum2 = 0;

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

		sum1 += flag[i];

		if (flag[i] == 1) sum2 += penalty[i];

	}

	cout << sum1 << " " << sum2 << endl;

	return 0;

}

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

#include <map>

#include <cmath>

#include <queue>

#include <vector>

#include <string>

#include <algorithm>

#include <functional>

using namespace std;

#pragma warning (disable: 4996)



int N, M;

int A[1 << 18];

bool used[1 << 18];



int main() {

	cin >> N >> M;

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

		int a; string b; cin >> a >> b;

		if (b == "WA" && used[a] == false) { A[a] += 1; }

		if (b == "AC") { used[a] = true; }

	}



	int v1 = 0, v2 = 0;

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

		if (used[i] == false) continue;

		v1 += 1; v2 += A[i];

	}

	cout << v1 << " " << v2 << endl;

	return 0;

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

#include <cstring>

#include <stdio.h>

#include <cmath>

using namespace std;

const int N=1e5+200;

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

int memo[N];

int dp(int i)

{

    if(i>n)

        return oo;

    if(i==n)

        return 0;

    int &ret=memo[i];

    if(ret!=oo)

        return ret;

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

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

        return ret;



}

int main()

{

    memset(memo,'?',sizeof memo);

    oo=memo[0];



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

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

    {

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

    }

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

    return 0;

}


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



using namespace std;



int main()

{

    int N, K;

    cin >> N >> K;



    int h[N], dp[N];



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

    {

        cin >> h[i];

        dp[i]=1000000000;

    }

    dp[N-1]=0;

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



    for(int i=N-3;i>=0;i--)

    {

        for(int j=i+1;j<min(N, i+K+1);j++)

        {

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

        }

    }

    cout << dp[0];

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

#define INF 0x3f3f3f3f

using namespace std;

const int maxn = 1e6+10;

int a[maxn];

int dp[maxn];

int main()

{

    int n,k;

    memset(dp,INF,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-1;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]));

        }

    }

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

    return 0;

}


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

#define IO ios::sync_with_stdio(0), cin.tie(0)

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 5;

const int inf = ~0u >> 1;

int d[maxn], h[maxn];

int main() {

    IO;

    int n, k;

    cin >> n >> k;

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

        cin >> h[i];

    }

    d[1] = 0;

    d[2] = abs(h[2] - h[1]);

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

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

        //cout << "i = " << i << " j = " << 1 << " d[i] = "  << d[i] <<endl;

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

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

            //cout << "i = " << i << " j = " << j << " d[i] = "  << d[i] <<endl;

        }

    }

    cout << d[n] << endl;

    return 0;

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

#include<cstdio>

#include<algorithm>

using namespace std;

int main(void){

	int n,k;

	int m;

	cin>>n>>k;

	int count = 0;

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

		cin>>m;

		if(m>=k)count+=1;

	} 

	cout<<count<<endl;

	return 0;

}

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



int main()

{

    int n,k,ans=0;

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

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

    {

        int x;

        scanf("%d",&x);

        if(x>=k)ans++;

    }

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

    return 0;

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

using namespace std;



//  c0 c1 c2 c3 c4 c5 c6

//  a0 a1 a2 a3 a4 a5 a6

const int tam = 1e5+10;

long long dp[tam];

long long h[tam];

int k;

long long INF = 1e18;





int solve( int i  ) {

    if( i <= 1 ) return abs(h[0]-h[i]);

    long long &ans = dp[i];

    if( ans != -1 ) return ans;

    ans = INF;

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

        if( i-j >= 0 )

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

    }

    return ans;

}



int main() {

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

    int n;

    cin >> n >> k;

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

        cin >> h[i];

    } 

    // dp[0] = 0;

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

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

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

    //     if( j <= i ) {

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

    //     }

    // }

    // cout << dp[n-1] << '\n';

    memset( dp, -1, sizeof dp );

    cout << solve(n-1) << '\n';

    return 0;

}

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



using namespace std;



int solve(const int stones_height[], int memo[], const int &n, const int &k){

    int ans;

    if(memo[n] != -1) ans = memo[n];

    else if(n == 1) return 0;

    else{

        ans = abs(stones_height[n] - stones_height[n - 1]) + solve(stones_height, memo, n - 1, k);

        for(int i = 2; n - i >= 1 && i <= k; i++){

            ans = min(ans, abs(stones_height[n] - stones_height[n - i]) + solve(stones_height, memo, n - i, k));

        }

    }

    return memo[n] = ans;

}



int main(){

    int n, k;

    while(scanf("%d %d", &n, &k) != EOF){

        int stones_height[n + 1], memo[n + 1];

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

            scanf("%d", &stones_height[i + 1]);

            memo[i + 1] = -1;

        }

        printf("%d\n", solve(stones_height, memo, n, k));

    }

    return 0;

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

using namespace std;

#define ll long long int 

int main()



{

	ll n,re=0,bl=0,gr=0,res,wr,i,j,k;

	string s;

	scanf("%lld",&n);

	getchar();

	getline(cin,s);

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

	{

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

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

		if(s[i]=='B')bl++;

	}

res=re*gr*bl;

wr=0;

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

{

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

	{

		//j-i=k-j

		k=2*j-i;

	  if( k<= n){

                if(s[i-1] != s[j-1] && s[k-1] != s[j-1] && s[i-1] != s[k-1]){

                	wr++;

			}

	}

}

}

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

}

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

}