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



using namespace std;



const int maxn=110000;

int n,k,h[maxn],f[maxn];

int main(){

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

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

	memset(f,0x3f,sizeof(f)),f[1]=0;

	for(int i=2;i<=n;i++) for(int j=1;j<i&&j<=k;j++) f[i]=min(f[i],f[i-j]+abs(h[i]-h[i-j]));

	printf("%d",f[n]);

    return 0;

}

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

#include <fstream>

#define inf INFINITY

#define file freopen( "input.txt" , "r" , stdin) ; freopen( "output.txt" , "w" , stdout) ; 

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

#define _3102_ main()

#define endl '\n'

typedef long long ll ;

typedef unsigned long long ull ; 

typedef long double ld ; 

using namespace std ;

const int N = 1e5+100  ; 

const ll mod = 1e9 + 7  ;







int _3102_ {

    Gamed

    ll n , k , arr[N] , dp[N] ; 

    cin >> n >> k ; 

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

        cin >> arr[i] ; 

    }

    dp[0] = 0 ;  

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

        ll ans = inf , cnt = k; 

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

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

        }

        dp[i] = ans ; 

    }

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

    return 0;

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

#include <cstdio>

#include <string>

#include <vector>

using namespace std;



int main()

{

    string s;

    vector<char> A;

    while(cin>>s)

    {

        int a=s.size();

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

        {

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

            {

            A.push_back('0');

            }

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

                    {

                    A.push_back('1');

                    }

                    else if(!A.empty())

                        {

                        A.pop_back();

                        }

        }

        int b=A.size();

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

        {

            cout<<A[i];

        }

A.clear();

        cout<<endl;

    }

    return 0;

}


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

#include<cstring>

using namespace std;

char s[105],c[105];

int main()

{

	int n = 0;

	scanf("%s",s);

	int len = strlen(s);

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

	{

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

		{

			n--;

			if(n < 0) n = 0;

		}

		else c[n++] = s[i];

	}

	c[n] = '\0';

	printf("%s",c);

	return 0;

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

#include<cstring>

#include<string>

#include<cstdio>

using namespace std;

	int main(){

		int n;

		cin>>n;

		string s,ans;

		cin>>s;

		if(n>=s.size())

			cout<<s<<endl;

		else{

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

				ans+=s[i]; 

			ans+='.',ans+='.',ans+='.';

			cout<<ans<<endl;

		} 

	}

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



int main(){

	int k;

	char word[100];

	scanf("%d", &k);

	scanf("%s", &word);

	

	int len = 0;

	

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

		len++;

	}

	

	if(len <= k){

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

	}

	else{

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

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

		}

		printf("...\n");

	}

	return 0;

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



using namespace std;



#define FOR(i,s, t) for(int i = s; i < t; i++)

#define ALL(a)  a.begin(), a.end()

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

#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define SORT(a) sort(ALL(a))

using VI = vector<int>;

using LL = long long;

using VVL = vector<vector<LL>>;

using VL = vector<LL>;



const LL LINF = 1e18;



int editDistance(string& s, string& t) {

	VVL dp(1010, VL(1010, 0));



	FOR(i, 0, 1010) {

		dp[i][0] = i;

		dp[0][i] = i;

	}

	FOR(i, 0, SZ(s)) {

		FOR(j, 0, SZ(t)) {

			int cost = (s[i] == t[j]) ? 0 : 1;

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

		}

	}

	return dp[s.size()][t.size()];

}



signed main() {

	string s, t;

	cin >> s >> t;

	cout << editDistance(s, t) << endl;

}








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

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

const int INF = 1e9;

const ll LINF = 1e18;

template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }

template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }

template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }

template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }



/*

 <url:>

 問題文============================================================

 =================================================================

 解説=============================================================

 

 ================================================================

 */





ll solve(){

    ll res = 0;

    string s1,s2; cin >> s1 >> s2;

    vector<vector<ll>> dp(s1.length()+1,vector<ll>(s2.length()+1,LINF));

    

    dp[0][0] = 0;

    for(int i = 0; i <= s1.length();i++) dp[i][0] = i;

    for(int j = 0; j <= s2.length();j++) dp[0][j] = j;

    

    for(int i = 1; i <= s1.length();i++){

        for(int j = 1; j <= s2.length();j++){

            dp[i][j] = min({dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+(s1[i-1]==s2[j-1]?0:1)});



        }

    }

    res = dp[s1.length()][s2.length()];

    return res;

}

int main(void) {

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

    auto ret = solve();

    cout << ret << endl;

    return 0;

}
// Slower C++ solution:
// Created by Kshitij Anand NSIT

#include <bits/stdc++.h>





using namespace std;





#define int long long

#define pb push_back

#define P pair<int,int>

#define F first

#define S second

#define vi vector<int>

#define vc vector<char>

#define vb vector<bool>

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

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

#define mp(a, b) make_pair(a, b)

#define min3(a, b, c) min(min(a, b), c)

#define min4(a, b, c, d) min(min(a, b), min(c, d))

#define max3(a, b, c) max(max(a, b), c)

#define max4(a, b, c, d) max(max(a, b), max(c, d))

#define fill(arr,val) memset(arr,val,sizeof(arr))

#define db(x)  cout<<#x<<" : "<<x<<endl





const int N = 1000000007;



int dp[100009];



int func(int arr[] , int n , int curr , int k){



	if(curr >= n){



		return 0;

	}



	if(curr == n-1)

		return 0;



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



	int ans = INT_MAX;



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



		if(curr + i <n){



		int temp = func(arr , n , curr+i , k);

		if(temp!=-1)

			ans = min(ans , abs(arr[curr] - arr[curr+i])  + temp);

		}

	}



	



	if(ans == INT_MAX)

		ans = -1;



	dp[curr] = ans;

	return ans;



}



void solve(){



    int n,k,b,c, ans=0, count=0, sum=0;

    cin>>n>>k;

    int arr[n];

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

      cin>>arr[i];

    }

    fill(dp , -1);

    ans = func(arr , n , 0 , k);

    cout<<ans<<endl;

}



int32_t main() {

    ios_base::sync_with_stdio(false);

    cin.tie(NULL); cout.tie(NULL);

    

    

  //  int t; cin>>t; while(t--)

    {     

      solve();

    }



  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.7927542563347991x):
// Created by Kshitij Anand NSIT

#include <bits/stdc++.h>





using namespace std;





#define int long long

#define pb push_back

#define P pair<int,int>

#define F first

#define S second

#define vi vector<int>

#define vc vector<char>

#define vb vector<bool>

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

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

#define mp(a, b) make_pair(a, b)

#define min3(a, b, c) min(min(a, b), c)

#define min4(a, b, c, d) min(min(a, b), min(c, d))

#define max3(a, b, c) max(max(a, b), c)

#define max4(a, b, c, d) max(max(a, b), max(c, d))

#define fill(arr,val) memset(arr,val,sizeof(arr))

#define db(x)  cout<<#x<<" : "<<x<<endl





const int N = 1000000007;



int func(int arr[] ,  int n , int k){



	int dp[n];



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

		dp[i] = INT_MAX;

	}

	dp[0] = 0;



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





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



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



			if(i-j >=0){

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



			}

		}





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

	}



	return dp[n-1];



}



void solve(){



    int n,k,b,c, ans=0, count=0, sum=0;

    cin>>n>>k;

    int arr[n];

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

      cin>>arr[i];

    }



    ans = func(arr , n , k);



    cout<<ans<<endl; 

}



int32_t main() {

    ios_base::sync_with_stdio(false);

    cin.tie(NULL); cout.tie(NULL);

    

    

  //  int t; cin>>t; while(t--)

    {     

      solve();

    }



  return 0;

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

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

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

int main()

{

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

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

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

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

	f[1]=0;

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

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

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

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

	return 0;

}

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

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

#define ll long long

#define fastIO cout << fixed << setprecision(9), ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

double const EPS = 1e-9, PI = acos(-1);

const int N = 1e5 + 9, M = 5e2 + 9, OO = 1e9 + 7, MOD = 1e9 + 9;

const ll inf = 1e18;



ll dp[N], h[N];



int main() {

  fastIO;

#ifdef LOCAL

  freopen("input.in", "rt", stdin);

#endif

  int n, k;

  cin >> n >> k;

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

    cin >> h[i], dp[i] = inf;

  dp[0] = 0;

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

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

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

  }

  cout << dp[n-1];

  return 0;

}


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



#define el				'\n'

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

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

#define clr(v, d)		memset(v, d, sizeof(v))



double const EPS = 1e-8, PI = acos(-1);

const int N = 1e5 + 9, M = 1e5 + 9, OO = (int) 1e6 + 1;

const long long MOD = 1e9 + 7;



typedef long long ll;



void OUTPUT() {

	cout << fixed << setprecision(0);

	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

}



void READ() {

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

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

}

ll n, k, heights[N], mem[N];



ll dp(int i) {

	if (i >= n)

		return OO;

	if (i == n - 1)

		return 0;

	if (mem[i] != -1)

		return mem[i];

//	mem[i] = OO;

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

		if (j == 1)

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

		else

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

	}

	return mem[i];

}



int main() {

//	READ();

	OUTPUT();

	clr(mem, -1);

	cin >> n >> k;

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

		cin >> heights[i];

	}

	cout << dp(0);



	return 0;



}


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

#include <cmath>



using namespace std;

int k,j,i,n,h[100005];

long long dp[100005];

int main()

{

    cin>>n>>k;

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

        cin>>h[i];

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

        dp[i]=1e17;

    dp[1]=0;

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

    {

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

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

    }

    cout<<dp[n];

    return 0;

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

#include <math.h>

using namespace std;

int main() {

    int k,x;

    cin>>k>>x;

    if(k==1) {

        cout << x<<endl;

    }

    else{

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

            cout<<-1*(k-i)+x<<" ";

        }

    }

    system("pause");

}


// Faster C++ solution for the same problem (measured speedup: 5.232941641863548x):
////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 <bits/stdc++.h>

    using namespace std;

    #define INF 2000000000

    typedef long long int ll;

    typedef pair<ll,ll> ii;

    typedef pair<ii,ll> iii;

    typedef vector<ll> vi;

    typedef vector<ii> vii;

    #define getbit(n,i) (((n)&(1<<(i)))!=0)

    #define setbit0(n,i) ((n)&(~(1<<(i))))

    #define setbit1(n,i) ((n)|(1<<(i)))

    #define togglebit(n,i) ((n)^(1<<(i)))

    #define lastone(n) ((n)&(-(n)))

    #define read freopen("debug\\in.txt","r",stdin)

    #define write freopen("debug\\out.txt","w",stdout)

    #define fi first

    #define se second

    #define getI(a) scanf("%d",&a)

    #define getII(a,b) scanf("%d%d",&a,&b)

    #define PI (acos(-1))

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

    #define mod (1000000007)

    #define asz 500005

    #define pb push_back

    #define ppf pop_front

    #define ppb pop_back

    #define pf push_front

    ll k,n;

    ll dp[200005];

    ll h[200005];

   // ll mini=1e9;

    ll recurse(ll pos){

      if(pos==n)

      return 0;

      ll i;

      if(dp[pos]!=-1)

      return dp[pos];

      ll mini=1e9;

      for(i=1;i<=k&&pos+i<=n;i++){

        mini=min(mini,recurse(pos+i)+abs(h[pos]-h[pos+i]));

      }

      return dp[pos]=mini;

    }

    int main()

    {

        fastread;

        ll i,j,l,m,t,q,r,c;

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

        dp[i]=-1;

        cin>>n>>k;

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

        cin>>h[i];

        cout<<recurse(1);

        return 0;

    }

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

using namespace std;

#define INF 2000000000

typedef long long int ll;

typedef pair<ll,ll> ii;

typedef pair<ii,ll> iii;

typedef vector<ll> vi;

typedef vector<ii> vii;

#define getbit(n,i) (((n)&(1<<(i)))!=0)

#define setbit0(n,i) ((n)&(~(1<<(i))))

#define setbit1(n,i) ((n)|(1<<(i)))

#define togglebit(n,i) ((n)^(1<<(i)))

#define lastone(n) ((n)&(-(n)))

#define read freopen("debug\\in.txt","r",stdin)

#define write freopen("debug\\out.txt","w",stdout)

#define fi first

#define se second

#define getI(a) scanf("%d",&a)

#define getII(a,b) scanf("%d%d",&a,&b)

#define PI (acos(-1))

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

#define mod (1000000007)

#define asz 500005

#define pb push_back

#define ppf pop_front

#define ppb pop_back

#define pf push_front

ll a[500005];

ll dp[500006];

int main()

{

    ll n,i,j,k,l,m;

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

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

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

    	dp[i]=1e9;

	}

	dp[1]=0;

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

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

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

	}

	cout<<dp[n];

    return 0;

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



using namespace std;



int main(){

    int n,k;

    cin >> n >> k;

    int pedras[n], pd[n];

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

        int aux;

        cin >> aux;

        pedras[i] = aux;

        pd[i] = INT_MAX;

    }

    pd[0] = 0;

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

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

            pd[i+j] = min(pd[i+j],pd[i] + abs(pedras[i]-pedras[i+j]));

        }

    }

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

    return 0;

}

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

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

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

int main()

{

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

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

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

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

	f[1]=0;

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

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

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

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

	return 0;

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

using namespace std;

long long int arr[100009],crr[100009];

int main()

{

    long long int n,k, temp;



    cin>>n>>k;



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

    {

        cin>>crr[i];

    }

    arr[1] = 0;

    arr[2] = abs(crr[1]-crr[2]);

    if(n==2){cout<<abs(crr[1]-crr[2])<<endl;return 0;}



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

    {

        arr[i] = 1e18;

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

        {

            if( i-j>=1 )

            {

                //arr[i] = arr[i] + arr[i-j];

                temp = abs(crr[i] - crr[i-j])+arr[i-j];

                arr[i] = min(arr[i],temp);

            }else

            {

                break;

            }

        }

    }

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

//    {

//        cout<<arr[i]<<" ";

//    }

    cout<<arr[n]<<endl;

    return 0;

}


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

#include <algorithm>

#include <cmath>

using namespace std;



int h[(int)1e5], dp[(int)1e5], K, N;





int main()

{

	K = N = 0;

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

	{

		dp[j] = 1e9;

	}

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

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

	{

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

	}

	dp[1] = 0;

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

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

		}

	}

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

	return 0;	

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



using namespace std;

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

int f(int i = 0)

{

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

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

    dp[i] = 1e9;

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

      if( i+j < n )

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

    //cout << dp[i] << ' ' << i << endl;

    return dp[i];

}

int main()

{

    memset(dp,-1,sizeof dp);

    cin >> n >> k;

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

        cin >> a[i];

    cout << f();

    return 0;

}

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

using namespace std;

#define ll long long

int main()

{

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

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

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

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

    dp[n-1] = 0;

    for(int i=n-2; i>=0; --i)

    {

        dp[i] = 1e9;

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

        {

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

        }

    }

    cout << dp[0];

    return 0;

}
// Slower C++ solution:
//Tareq

//not acc

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int a,b;

    cin>>a>>b;

    for(int i=b-(a-1) ; i<=(b+(a-1)) ; i++)

    {

        cout<<i;

        if(i==(b+(a-1))) cout<<endl;

        else cout<<" ";

    }

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.219313065720167x):
////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 <bits/stdc++.h>

#include<iostream>

using namespace std;

int main()

{

    stack<char>s ;

    string str,m;

    cin>>str;

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

        if(str[i]!='B')

           s.push(str[i]);

        else{

            if(!s.empty())

               s.pop();

        }

    }

    

    while (!s.empty()) 

    { 

       m+= s.top(); 

        s.pop(); 

    } 

    reverse(m.begin(),m.end()); 

    cout<<m;

    return 0;

}


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



int main() {

  char s[11];

  scanf("%s", s);



  int idx = 0;

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

    if(s[i] == '0') s[idx++] = '0';

    else if(s[i] == '1') s[idx++] = '1';

    else if(s[i] == 'B' && idx > 0) idx--;

  }



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

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

  }

  return 0;

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

using namespace std;

typedef long long ll;

const int N=1e5+5;

#define endl '\n'



int a[N];



int main(){

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

	cout.setf(ios::fixed),cout.precision(3);

	int n,b,c,q,value;

	ll sum;

	cin>>n;

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

	sum=0;

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

		cin>>value;

		a[value]++;

		sum+=value;

	}

	cin>>q;

	while(q--){

		cin>>b>>c;

		sum+=1ll*(c-b)*a[b];

		a[c]+=a[b];

		a[b]=0;

		cout<<sum<<endl;

	}

	return 0;

}

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

using namespace std;

typedef long long ll;

int main()

{

	ll n,q,ans=0,a,b,c;

	cin>>n;

	map<ll,ll>m;

	while (n--)

	{

		cin>>a;

		ans+=a;

		m[a]++;

	}

	cin>>q;

	while (q--)

	{

		cin>>b>>c;

		ans+=m[b]*(c-b);

		m[c]+=m[b];

		m[b]=0;

		cout<<ans<<"\n";

	}

}