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

#include<iostream>

#include<algorithm>

#include<cstring>

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

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

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

		}

	}

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

	return 0;

}

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

using namespace std;

int main()

{

    int n,k;

    cin>>n>>k;

    int h[n];

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

    {

        cin>>h[i];

    }

    long long int dp[n];

    fill(dp,dp+n,1e9);

    dp[0]=0;

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

    {

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

        {

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

        }

    }

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

}


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

#include <array>

#include <vector>

#include <iomanip>

#include <string>

#include <cmath>

#include <array>

#include <algorithm>

#include <queue>

#include <map>

using namespace std;



typedef  pair<int,int> P;

typedef long long LL;



const LL  INF=1<<31;







int main(){

     int n,k;

     cin>>n>>k;

     int h[100000];

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

          cin>>h[i];

     }

     LL dp[100001];



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

           dp[i]=INF;

      }

            dp[0]=0;

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







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

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

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



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

          }

     }     



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





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

    

using namespace std;

int nummer;

vector<long long >dp(100001,900000000000000);

vector<long long>num;

long long  erg(int n){

	if(dp[n]!=900000000000000){

		return dp[n];

	}

	if(n<0){

		return 900000000000000;

	}

	if(n==0){

		return 0;

	}

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

		if(n-i<0){

			break;

		}

		dp[n]=min(dp[n],erg(n-i)+(max(num[n],num[n-i])-min(num[n],num[n-i])));

	}

	return dp[n];

}

int main() {

	int menge,numm;

	cin>>menge>>nummer;

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

		cin>>numm;

		num.push_back(numm);

	}

cout<<erg(menge-1);

    return 0;

}

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

#include <vector>

using namespace std;

int main(){

	int n,k;

	cin>>n>>k;

	vector <int> h(n),dp(n,INT_MAX);

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

			if(i+j<n){

			dp[i+j]=min(dp[i+j],dp[i]+abs(h[i+j]-h[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;



	

	/* constants */

	#define inf (int)1e+9

	#define VIS 1

	#define UNVIS 0

	#define null NULL

	#define MAX (int)1e+6

	#define MIN -(int)1e+6

	

// ------------------------------------------------------------------------



int n, k;

vector<int> v;

vector<int> memo((int)1e5+5,-1);



int minCost(int pos) {



	if (memo[pos]!=-1)

		return memo[pos];



	if (pos==(n-1))

		return 0;



	if (pos>n)

		return inf;



	int answer=inf;

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

		answer=min(answer,minCost(pos+i)+abs(v[pos]-v[pos+i]));

	}



	memo[pos]=answer;

	return answer;

}





int main()

{

	

	cin.tie(NULL);

	cout.tie(NULL);



	/*Start*/

	



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

	

	

	v.resize(n);



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

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





	cout<<minCost(0)<<endl; 

    

    return 0;

}


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

using namespace std;



int main(){

	

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

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

	

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

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

		

		dp[i] = (i != 0) * 1000000000;

		

		for(int j = i - 1; j >= 0 && j >= i - k; j--) dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]));

	}

	

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

#define endl '\n'

#define ll long long

using namespace std;



const int MXN = 1e5 + 5;

int n, k;

int h[MXN];

int dp[MXN];



int Dp(int idx) {

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

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

    int ans = 1e9;

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

        ans = min(ans, Dp(i) + abs(h[idx] - h[i]));

    }

    return dp[idx] = ans;

}



int main() {

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

    cin >> n >> k;

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

        cin >> h[i];

    }

    memset(dp, -1, sizeof dp);

    cout << Dp(0) << endl;

    return 0;

}

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

}

// 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):
#define rep(i, n) for (int i = 0; i < (n); i++)

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

using P = pair<int, int>;

const int MOD = 1000000007;



int main() {

    int A, B, C;

    cin >> A >> B >> C;



    bool isYes = false;

    rep(i, 1000) { // O(10^8)

        rep(j, 1000) {

            if ((A * i) - (B * j) == C)

                isYes = true;

        }

    }



    string ans = isYes ? "YES" : "NO";

    cout << ans << endl;



    return 0;

}

// Optimized solution to the same problem (faster):
#define rep(i, n) for (int i = 0; i < (n); i++)

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

using P = pair<int, int>;

const int MOD = 1000000007;



int main() {

    int A, B, C;

    cin >> A >> B >> C;



    bool isYes = false;

    rep(i, B) {

        if (((i + 1) * A) % B == C)

            isYes = true;

    }



    string ans = isYes ? "YES" : "NO";

    cout << ans << endl;



    return 0;

}

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

using ll = long long;

using namespace std;



int main() {

  int A,B,C;

  cin>>A>>B>>C;

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

    if ((A*i-C)%B==0&&(A*i-C)>=0){

      cout << "YES"<<endl;

      return 0;

    }

  }

  cout << "NO"<<endl;

  return 0;

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

#include<cstring>

using namespace std;

char s[1000009];

int main(){

	int a;

	cin>>a>>s;

	if(strlen(s)>a)

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

	cout<<s[i];

	cout<<"...";

	}

	else cout<<s<<endl;

	

	

}

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

#include<string.h>

int main(){

	int k;

	char s[105];

	scanf("%d",&k);

	getchar();

	scanf("%s",&s);

	if(strlen(s)>k){

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

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

		}

		printf("...");

		printf("\n");

	}

	else{

		int l = strlen(s);

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

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

		printf("\n");

	}

}

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

using ll = long long;



#define int ll

#define FOR(i,n,k) for(int i=n;i<k;i++)

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



const int N = 1e5 + 5;

int dp[N];



int32_t main()

{

    IOS;

    memset(dp,9999,sizeof(dp));

    int n,k;

    cin>>n>>k;

    int a[n+1];

    FOR(i,1,n+1) cin>>a[i];

    dp[1] = 0;

    FOR(i,2,n+1)

    {

        FOR(j,1,k+1)

        {

            if(i-j > 0)

            {

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

            }

        }

    }

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

    return 0;

}

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

using namespace std;



using ll = long long;



#define int ll



const int INF = 1e9 + 5;



int32_t main()

{

	int n,k;

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

	vector<int> h(n);

	for(int& x : h)

	{

		scanf("%lld", &x);

	}

	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(h[i] - h[j]));

			}

		}

	}

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

typedef long long ll;

typedef long long int lli;

typedef long double ld;

const int oo = 1e9;

const int mod = 1e9+9;

/*ll gcd(ll x, ll y){return (y ? gcd(y, x%y) : x); }

*ll lcm(ll x, ll y){return x*(y/gcd(x,y));}

*void exEuclid(int a, int b){

	if(b==0){x = 1; y=0; d=a; return ;}

	exEuclid(b, a%b);

	int x1=y;

	int y1=x-(a/b)*y;

	x=x1;

	y=y1;

} 

* */

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

const int nax = 1e5+103;

int n, k;

int dp[nax];

int a[nax];

int f(int i){

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

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

	int ans = abs(a[i]-a[i+1])+f(i+1);

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

		if(i+j<n) ans = min(ans, abs(a[i]-a[i+j])+f(i+j));

	}

	return dp[i]=ans;

}

int main(){

	cin>>n>>k;

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

	memset(dp, -1, sizeof dp);

	cout<<f(0)<<endl;

	return 0;

}


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

}


// 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()

{

	string s,ans;

	int i,k;

	cin>>k;

	cin>>s;

	if(s.length()>k)

	{

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

		{

			ans=ans+s[i];

		}

		ans.append(3,'.');

	}

	else

	ans.assign(s);

	cout<<ans<<endl;

	return 0;

 } 

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

	}

// 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 n,h[100005],c[100005],k;



int main()

{

    cin>>n>>k;

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

        cin>>h[i];

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

        c[i] = abs(h[0] - h[i]);



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

    {

        long long m = 1e10;

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

        {

            if ((c[i-j] + abs(h[i] - h[i-j])) <= m)

                m = c[i-j] + abs(h[i] - h[i-j]);

            c[i] = m;

        }

    }

    cout<<c[n-1];

}


// Optimized solution to the same problem (faster):
//才不露白

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

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

//比如从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;

}

// 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 rep(i,a,n) for(int i=a;i<n;i++)

#define repr(i,a,n) for(int i=a;i>=n;i--)

#define INF 999999999

#define INF_M 2147483647

#define pb(a) push_back(a)

using namespace std;

typedef pair<int, int> pii;

typedef long long int ll;



vector<int> erat(int n) {

    vector<int> primes(n);

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

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

        if (primes[i])

            for (int j = i*i; j < n; j+=i) primes[j] = 0;

    // ?´???°?????????vector???????´?????????´????????\?????????????????? (0 ??§??????????´??????¨??????)

    primes.erase(remove(primes.begin(), primes.end(), 0), primes.end());

    return primes;

}



int main() {

	vector<int> v = erat(50000);

	int n;

	while(cin >> n) {

		if(n == 0) break;

		int ans = 0;

		rep(i,0,v.size()) {

			if(v[i] > n / 2) break;

			else if((n-v[i]) != 0 && *lower_bound(v.begin(), v.end(), n-v[i]) == n-v[i]) ans++;

		}

		cout << ans << endl;

	}

}

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

int main()

{

	int n;

	char prime[50001];

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

		prime[i] = 1;

	prime[0] = 0; prime[1] = 0;

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

		if(!prime[i]) continue;

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

			prime[j] = 0;

	}

	while(scanf("%d\n", &n), n){

		int cnt = 0;

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

			if(prime[i] && prime[n - i])

				cnt++;

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

	}

	return 0;

}

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

using namespace std;



int main()

{

  bool is_prime[100000];

  is_prime[0] = is_prime[1] = false;

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

    is_prime[i] = true;

  }



  for(int i=2; i*i<100000; i++){

    if(is_prime[i]){

      for(int j=i*i; j<100000; j+=i){

        is_prime[j] = false;

      }

    }

  }



  while(1){

    int n;

    cin >> n;



    if(n == 0)

      break;



    int cnt=0;



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

      if(is_prime[i] && is_prime[n-i])

        if(i+(n-i) == n) cnt++;

    }



    cout << cnt << endl;

  }

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

#include<string.h>

#include<iostream>

using namespace std;

const int mod = 1e9 + 7;



int main()

{

	long long ans = 1, i;

	int n;

	scanf("%d", &n);

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

		ans = (ans % mod) * (i % mod) % mod;

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



}

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

int main ()

{

    int i,n;

    long long s;

    scanf("%d", &n);

    s = 1;

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

    {

        s *= i;

        s %= (int)1e9+7;

    }

    printf ("%d", s);

}


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

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

using namespace std;



using ll = long long;

#define pb push_back

#define fastread ios_base::sync_with_stdio(false);cin.tie(NULL);

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

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

#define pii pair<int, int>

#define pll pair<ll, ll>



const int maxn = 1e5 + 5;

ll dp[maxn];

int n, k, arr[maxn];

ll inf = 1e11;



ll call(int i){

	if(i >= n-1)return 0;

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

	ll ret = inf;

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

		if(i+j <= n-1)ret = min(ret, abs(arr[i] - arr[i+j]) + call(i+j));

	}

	return dp[i] = ret;

}



int main(){

	//file

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

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

	memset(dp, -1, sizeof dp);

	cout<<call(0)<<endl;

}

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

using namespace std;



const int maxn = 1e5 + 5; 

int a[maxn];

long long dp[maxn];



int main(){

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

	int n, k;

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

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

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

	}

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

	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]-a[i+j]));

			}

		}

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

}

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





}