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



using namespace std;



int n, k, m, s, ac[1000005],sub[100005],cor,pen;

int main()

{

    cin >> n >> m;

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

    {

        int x;

        char y[5];

        cin >> x >> y;

        if(y[0] == 'A')

        {

            ac[x] = true;

        }

        else if(ac[x] == false)

        {

            ++sub[x];

        }

    }

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

    {

        if(ac[i] == true)

            ++cor, pen += sub[i];

    }

    cout << cor << ' ' << pen;

    return 0;

}


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

#include <map>

#include <string>

using namespace std;

long long n,m,i,p,nra,nrg;

string s;

bool ma[100005];

int nrgr[100005];

int main()

{

    cin>>n>>m;

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

    {

        cin>>p>>s;

        if(s=="AC")

        {

            if(ma[p]==false)

            {

                nra++;

                nrg+=nrgr[p];

            }

            ma[p]=true;

        }

        else

        {

            if(ma[p]==false)

                nrgr[p]++;

        }

    }

    cout<<nra<<' '<<nrg;

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

using namespace std;

 

#define MAX 200000

#define SENTINEL 1200000000

 

typedef long long hyper;

hyper cnt = 0;

 

void Merge(int* A, int left, int mid, int right)

{

    int R[MAX], L[MAX];

    int i, j, k, n1, n2;

    n1 = mid - left;

    n2 = right - mid;

    for(i = 0; i < n1; i++) L[i] = A[i + left];

    for(j = 0; j < n2; j++) R[j] = A[j + mid];

 

    L[n1] = SENTINEL;

    R[n2] = SENTINEL;

    i = j = 0;

 

    // sorting.

    for(k = left; k < right; k++){

 

        if(L[i] <= R[j]){ A[k] = L[i]; i++; }

 

        else{ A[k] = R[j]; j++; cnt = cnt + n1 - i; } // add n1 - i.

    }

}

 

void MergeSort(int* A, int left, int right)

{

    int mid;

    if(left + 1 < right){

        mid = (left + right) / 2;

        MergeSort(A, left, mid);

        MergeSort(A, mid, right);

        Merge(A, left, mid, right);

    }

}

 

int main()

{

    int i, n, A[MAX];

    cin >> n;

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



    MergeSort(A, 0, n);

    cout << cnt << endl;

 

    return 0;

}

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



#define MAX 200000

#define SENTINEL 1200000000



typedef long long hyper;

hyper cnt = 0;



void Merge(int* A, int left, int mid, int right)

{

    int L[MAX], R[MAX];

    int i, j, k, n1, n2;

    n1 = mid - left;

    n2 = right - mid;

    for(i = 0; i < n1; i++) L[i] = A[i + left];

    for(j = 0; j < n2; j++) R[j] = A[j + mid];



    L[n1] = SENTINEL;

    R[n2] = SENTINEL;

    i = j = 0;



    // sorting.

    for(k = left; k < right; k++){



        if(L[i] <= R[j]){ A[k] = L[i]; i++; }



        else{ A[k] = R[j]; j++; cnt = cnt + n1 - i; } // add n1 - i.

    }

}



void MergeSort(int* A, int left, int right)

{

    int mid;

    if(left + 1 < right){

        mid = (left + right) / 2;

        MergeSort(A, left, mid);

        MergeSort(A, mid, right);

        Merge(A, left, mid, right);

    }

}



int main()

{

    int i, n, A[MAX];

    scanf("%d", &n);

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



    MergeSort(A, 0, n);

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



    return 0;

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



using namespace std;

#define tam 100001

#define infinito 10001

int dp[tam],A[tam],n,k;

int solver(int index)

{

    if(dp[index] != -1)

        return dp[index];

    dp[index] = infinito;

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

    {

        if(dp[index-j] + abs(A[index]-A[index-j]) <  dp[index])

            dp[index] = solver(index-j) + abs(A[index]-A[index-j]);

    }

    return dp[index];

}

int main()

{

    cin>>n>>k;

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

        cin>>A[i];

    memset(dp,-1,sizeof dp);

    dp[0]=0;

    cout<<solver(n-1)<<"\n";

    return 0;

}


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

using namespace std;



const int maxn = 100050;

const int INF = 0x3f3f3f3f;

int a[100050];

int dp[maxn];



int main()

{

	int n,k;

	cin>>n>>k;

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

	    cin>>a[i];

	

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

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

	    dp[i] = INF;

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

	return 0;

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

using namespace std;

using ll = long long;

using ii = pair<int,int>;



const int mx = 2e5+5;



int n, m;

ll dp[1<<16];

int a[16][16];

ll values[1<<16];



ll fun(int mark){

    if(mark == 0) return 0;



    ll &ans = dp[mark];

    if(~ans) return ans;



    ans = LLONG_MIN;

    for(int cur=mark; cur>0; cur=(cur-1)&mark)

        ans = max(ans, values[cur]+fun(mark ^ cur));

    return ans;

}



int main(){

    cin.tie(nullptr);

    ios_base::sync_with_stdio(0);



    cin >> n;

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

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

            cin >> a[i][j];

    m = (1<<n) - 1;



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

        vector<int> v;

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

            if(i & (1<<j))

                v.push_back(j);

        ll tot = 0;

        for(int j=0; j<v.size(); j++)

            for(int k=j+1; k<v.size(); k++)

                tot += a[v[j]][v[k]];

        values[i] = tot;

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



    ll ans = fun(m);

    cout << ans << "\n";



    return 0;

}




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

using namespace std;

#define int long long

int n, a[20][20], val[100100], f[100000];

main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

    cin >> n;

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

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

            cin >> a[i][j];

    int tmp = (1 << n);

    for (int mask = 1; mask < tmp; mask++)

    {

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

            if ((mask >> i) & 1)

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

                    if ((mask >> j) & 1)

                        val[mask] += a[i][j];

    }

    for (int mask = 1; mask < tmp; mask++)

    {

        f[mask] = max(f[mask], val[mask]);

        for (int preMask = mask; preMask > 0; preMask = (preMask - 1) & mask)

            f[mask] = max(f[mask], f[preMask] + f[(mask ^ preMask)]);

    }

    cout << f[tmp - 1];

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

using namespace std;

typedef long long int ll;

typedef vector<ll> vl;

typedef vector<vector<ll>> vvl;

typedef vector<pair<ll,ll>> vp;

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

#define reep(i,n) for(ll i = n; i >-1; i--)

#define deb(variable) cout<<#variable<<"="<<variable<<endl

#define MMOD(i) ((i%MOD)+MOD)%MOD;

#define vec(i,j) vector<vector<ll>>(i,vector<ll>(j,0))

const ll INF=99999999999999999;

const ll MOD=128;

const ll MAX_N=500010;

ll a,b,c,d,e,x,y,z,k,m,n,l,q,ans=0;

vl v,v1;

vp p[100010];

string s;

ll solve(void){

    if(v.back()>v1[0])return 0;

    return v1[0]-v.back()+1;

}

int main(){

    cin>>n>>m;

    rep(i,m){

     cin>>a>>b;

     v.push_back(a);

     v1.push_back(b);

    }

 

    sort(v.begin(),v.end());

    sort(v1.begin(),v1.end());

 

    cout<<solve()<<endl;

}

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

using namespace std;

typedef long long int ll;

typedef vector<ll> vl;

typedef pair<ll, ll> PP;

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

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

bool chmin(ll & a, ll  b) { if (b < a) { a = b; return 1; } return 0; }

bool chmax(ll & a, ll b) { if (b > a) { a = b; return 1; } return 0; }

const ll INF = 999999999999999;

const ll MOD = 1000000007;

const ll MAX_N=500010;

ll a, b, c, d, e, f, p, t, x, y, z, q, m, n, r, h, k, w, l, ans;

int main() {

    cin>>n>>m;

    x=INF;

    y=0;

    rep(i,m){

        cin>>a>>b;

        x=min(b,x);

        y=max(a,y);

    }



    cout<<max(0LL,x-y+1)<<endl;

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



using namespace std;



int main()

{

    int n{};

    int k{};

    cin >> n >> k;

    int h{};

    int cnt;

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

        cin >> h;

        if (h>=k)

            ++cnt;

    }

    cout << cnt << endl;

    return 0;

}


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

typedef long long ll;

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

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

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please





int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);





	int N, K;

	cin >> N >> K;

	

	int kotae = 0;

	rep(i, N) {

		int H;

		cin >> H;



		if (H >= K) kotae++;

	}



	cout << kotae << endl;





	Would you please return 0;

}

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

#include<cstdio>

using namespace std;

typedef long long ll;

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

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

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



const int cm = 1 << 19;

char cn[cm], * ci = cn;

inline int getint() {

	char C = *ci++;

	int A = C - '0';

	while ((C = *ci++) >= '0') A = A * 10 + C - '0';

	return A;

}



int main() {

	//cin.tie(0);

	//ios::sync_with_stdio(false);



	fread(cn, 1, cm, stdin);



	int N = getint(), K = getint();

	int kotae = 0;

	rep(i, N) if (getint() >= K) kotae++;

	printf("%d", kotae);



	Would you please return 0;

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

#include <string>



#define MAXN 1000



using namespace std;



string S, T;



string mov(string str, int N)

{

    string strr = str;

    int i = 0, j;

    while(i < N)

    {

        char c = strr[strr.length() - 1];

        for(j = strr.length() - 1; j >  0; j--)

        {

            strr[j] = strr[j - 1];

        }

        strr[0] = c;

        i++;

    }

    return strr;

}

int main()

{

    cin>>S;

    cin>>T;

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

    {

        if(mov(S, i) == T)

        {

            printf("Yes\n");

            return 0;

        }

    }

    printf("No\n");

    return 0;

}


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

#include <cstring>

#include <algorithm>

char s[110];

char t[110];



int main(){

    scanf("%s%s", s, t);

    int len1 = strlen(s);

    int len2 = strlen(t);

    if(len1 != len2){

        printf("No\n");

        return 0;

    }

    else{

        int len = len1;

        if(strcmp(s,t) == 0){

            printf("Yes\n");

            return 0;

        }else{



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

                char temp[110];

                strcpy(temp, s);

                std::reverse(temp, temp + len - i);

                std::reverse(temp + len - i, temp + len);

                std::reverse(temp, temp + len);

                if(strcmp(temp, t) == 0){

                    printf("Yes\n");

                    return 0;

                }

            }



        }

    }

    printf("No\n");

    return 0;



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



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

    {

        cin>>num[i];

    }

    t=tani(1);

    cout<<t<<endl;

    return 0;

}




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

#include<cstring>

#include<algorithm>

#include<cstdio>

using namespace std;

#define MAXN 100000 + 10

#define ll long long int

ll N[MAXN];

ll dp[MAXN];

#define INF 0x3f3f3f3f;

int main()

{

    ll n,k;

    cin>>n>>k;

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

        cin>>N[i],dp[i] = INF;

    dp[0] = 0;

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

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

            if(j >= 0)

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

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

    return 0;

}

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

using namespace std;



int main() {

	long long n, N = 1e5+7, h, q, b, c, s = 0, a[N];

	memset(a, 0, sizeof(a));

	cin >> n;

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

		cin >> h;

		s += h;

		a[h]++;

	}

	cin >> q;

	while(q--){

		cin >> b >> c;

		s += a[b] * (c - b);

		cout << s << '\n';

		a[c] += a[b];

		a[b] = 0;

	}

}

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

using namespace std;

int a[100005];

long long sum1;

int k;

int A,B;

int main()

{

	int x;

	int n;

	cin>>n;

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

	{

		cin>>x;

		a[x]++;

		sum1+=x;

	}

	cin>>k;

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

	{

		cin>>A>>B;

		a[B]+=a[A];

		sum1+=(B-A)*a[A];

		a[A]=0;

		cout<<sum1<<endl;

	}

}
// Slower C++ solution:
//g++ -std=gnu++14 a.cpp

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

#include <algorithm>

#include <bitset>

#include <complex>

#include <deque>

#include <iostream>

#include <istream>

#include <iterator>

#include <map>

#include <queue>

#include <set>

#include <stack>

#include <string>

#include <vector>

#include <tuple>

#include <iomanip>

#include <random>

#include <math.h>



using namespace std;



#define ll long long

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

ll MOD = 1e9 + 7;

int INF = 1 << 30;

ll INFL = 1LL << 60;



int main(){

  int  N,K;

  cin >> N >> K;

  vector<int> h(1000000);

  vector<int> dp(1000000, INF);

  for(int i = 1;i <= N;i++) cin >> h.at(i);

  dp[1] = 0;

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

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

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

    }

  }

  cout << dp[N] << endl;

}


// Faster C++ solution for the same problem (measured speedup: 3.5964938437749834x):
//g++ -std=gnu++14 a.cpp



#include <algorithm>

#include <bitset>

#include <complex>

#include <deque>

#include <iostream>

#include <istream>

#include <iterator>

#include <map>

#include <queue>

#include <set>

#include <stack>

#include <string>

#include <vector>

#include <tuple>

#include <iomanip>

#include <random>

#include <math.h>



using namespace std;



#define ll long long

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

ll MOD = 1e9 + 7;

int INF = 1 << 30;

ll INFL = 1LL << 60;



int main(){

  ll N,K;

  cin >> N >> K;

  vector<ll> h(100010);

  rep(i,N){

    cin >> h[i];

  }

  vector<ll> dp(100010,INFL);

  dp[0] = 0;

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

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

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

    }

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

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

  }

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

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



// #include <ext/pb_ds/assoc_container.hpp>

// #include <ext/pb_ds/tree_policy.hpp>

// #include <ext/pb_ds/detail/standard_policies.hpp>



using namespace std;

// using namespace __gnu_pbds;



#define int ll

#define endl "\n"

#define pb push_back

#define mp make_pair

#define ff first

#define ss second

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

#define vi vector<int>

#define pii pair<int,int>

#define For(i,s,e) for (ll i=(s); i<(e); i++)

#define MAX 500005

#define initialize(arr,elem) memset(arr,elem,sizeof(arr))



typedef long long ll;

// typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int memo[MAX], arr[MAX];

int k = 2;

int solve(int i){

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

	if (i==1) return memo[i] = 0;

	int dp = 100000000000000;

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

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

	}

	return memo[i] = dp;

}

signed main()

{

	ios_base::sync_with_stdio(false);

	cin.tie(NULL);

	cout.tie(NULL);

		

	

	int n;

	cin>>n>>k;

	initialize(memo,-1);

	For(i,1,n+1) cin>>arr[i];

	cout<<solve(n)<<endl;

	// For(i,1,3) cout<<memo[i]<<" ";







	return 0;

}


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

 

using namespace std;



typedef long long ll;

#define int ll

#define pb push_back

const int INF = 1e18;



signed main(){



	ios_base::sync_with_stdio(false);

	cin.tie(0);



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

	int cost[n+1];

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

		cin>>cost[i];



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

	dp[1] = 0;

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

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

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

	}

	cout<< dp[n];





	return 0;

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

using namespace std;





int n,k, heights[100005];

const int INF = 2000000000;

int main(){

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

    cin >> n >> k;

    int dp[n];

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

        cin >> heights[i], dp[i] = INF;

    dp[0] = 0;

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

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

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

        }

    }

    cout << dp[n-1];

    

}

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

#include <algorithm>

#include <vector>

using namespace std;

 

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

int main(){

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

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

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

	}

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

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

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

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

		}

	}

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

	return 0;

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



using namespace std;



int dp[(int)1e5+105];

int main()

{



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







    fill(dp, dp+(int)1e5+105 , INT_MAX );



    dp[1] = 0;

    int n,k;

    cin>>n>>k;

    vector <int> v(n+k+5,0);

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



        cin>>v[i];



    }

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

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

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

    }

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

}


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

/**

*   author: j o s e m a g o

*   date:

**/

using namespace std;

#pragma GCC optimize ("Ofast")

#define f first

#define s second

#define mp make_pair

#define lb lower_bound

#define ub upper_bound

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

#define mset(a,v) memset(a,v,sizeof(a))

#define pb push_back

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

#define rsz resize

#define ln "\n"



typedef double db;

typedef unsigned long long ull;

typedef long long ll;

typedef long double ld;

const ld PI = 2*acos(0.0);

const int MOD = 1000000007;

const int JJJ = 100009;









int main(){



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

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



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



    int N,k;

    cin >> N >> k;

    vector<int>h(N+k+1);

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

        cin >> h[i];

    }

    vector<int>dp(N+k+1,INT_MAX);

    dp[0] = 0;

    for(int i = 1;i < k;i++) dp[i] = abs(h[i]-h[0]);

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

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

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

        }

    }



//    for(int i = 0;i < N;i++) cerr<<dp[i]<<" ";

    cout<<dp[N-1];









    return 0;

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

using namespace std;

const int N = 100010;

const int oo = 1000000000;

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

int f(int pos) {

	if(dp[pos] != -1)

		return dp[pos];

	if (pos == (n - 1))

		return 0;

	if (pos > n)

		return oo;

	int answer = oo;

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

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

	return dp[pos] = answer;

}

int main(){

	cin >> n >> k;

	memset(dp, -1, sizeof dp);

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

		cin >> v[i];

	cout << f(0) << "\n";

    return 0;

}


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

using namespace std;



int main() {

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

    int n, k;

    cin >> n >> k;

    long long h[n], dp[n];

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

    return 0;

}
// Slower C++ solution:
/*

	Author: Luis Manuel D�az Bar�n (LUISMO)

	Problem:

	Online Judge:

	Idea:

*/

#include<bits/stdc++.h>

// Types

#define ll long long

#define ull unsigned long long

// IO

#define sf scanf

#define pf printf

#define mkp make_pair

#define fi first

#define se second

#define endl "\n"



using namespace std;



typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

const ll inf = 1e16 + 3;

const int mod = 1e9 + 7;

const int lim = 2e5 + 2;



int N, K;

ll hi[lim];



ll dp[lim];

int mark[lim];



ll DynamicProgramming(int idx)

{

    if(idx <= 0)

        return 0;



    if(mark[idx])

        return dp[idx];



    mark[idx] = true;



    DynamicProgramming(idx - 1);

    DynamicProgramming(idx - 2);





    int kidx =max(0,idx - K);

    ll aux = inf;

    for(int i = kidx; i < idx; i++)

    {

        ll curr = dp[i] + abs(hi[i] - hi[idx]);

        aux = min(aux, curr);

    }



    dp[idx] = aux;

    return dp[idx];

}





void solve()

{

    cin >> N >> K;

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

        cin >> hi[i];   



    ll answ = DynamicProgramming(N - 1);

    cout << answ;

}



void fastIO()

{

	cin.sync_with_stdio(false);

	cin.tie(0);

}



void IO()

{

	if(fopen("d:\\lmo.in","r") != NULL)

	{

		freopen("d:\\lmo.in","r",stdin);

	}

	else if(fopen("/media/Beijing/lmo.in","r") != NULL)

	{

		freopen("/media/Beijing/lmo.in", "r", stdin);

	}

}



int main()

{

	IO();



	fastIO();



	solve();

}


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

using namespace std;

#define MAX(a,b) (a>b?a:b)

#define MOD(a) (a>0?a:-(a))

#define custoate(i)

int main(){

  int npedras, maxpulo;

  scanf("%d %d",&npedras,&maxpulo);

  int hpedra[npedras],custoate[npedras];

  for (size_t i = 0; i < npedras; i++)

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

  custoate[0] = 0;

  int tempcost = 2147483647,k,tempcost2;

  for (size_t i = 1; i < npedras; i++,tempcost = 2147483647) {

    // printf("i = %d, tempcost = %d\n", i,tempcost);

    for (k= (maxpulo>i ? i : maxpulo); k > 0; k--) {

      // printf("k = %d ",k);

      tempcost2 = custoate[i-k] + MOD(hpedra[i-k]-hpedra[i]);

      if (tempcost > tempcost2)

        tempcost = tempcost2;

    }

    // printf("custo[%d] = %d",i,tempcost);

    custoate[i] = tempcost;

    // printf("\n\n");

  }

  printf("%d\n", custoate[npedras-1]);



}