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

using namespace std;

 

#define mp make_pair

#define pb push_back

#define st first

#define nd second

#define lb lower_bound

#define ub upper_bound

 

typedef long long ll;

typedef long double ld;

typedef pair<int,int> pi;

typedef pair<ll,ll> pll;

typedef vector<int> vi;

typedef vector<ll> vll;

typedef vector<pi> vpi;

typedef vector<pll> vpll;

 

const ll oo=1e18;

const int MOD=1000000007;

const int INF=1000000000;

const ld EPS=0.000000001;

 

int dp[100005],h[100005],n,k=2;

 

signed main() {

    ios_base::sync_with_stdio(NULL);

    cin.tie(NULL);

    cout.tie(NULL);

    memset(dp,0x3f3f,sizeof dp);

    dp[1]=0;

    h[0]=0;

    cin>>n>>k;

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

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

        }

    }

    cout<<dp[n];

    return 0;

}

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

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <sstream>

#include <queue>

#include <deque>

#include <bitset>

#include <iterator>

#include <list>

#include <stack>

#include <map>

#include <set>

#include <functional>

#include <numeric>

#include <utility>



#include <cmath>

#include <iomanip>



using namespace std;



int main()

{

  ios::sync_with_stdio(false);

  cin.tie(0);

  int n;

  cin >> n;

  int k;

  cin >> k;

  int h[n];

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

    int cur;

    cin >> cur;

    h[i] = cur;

  }

  int minCosts[n];

  minCosts[0] = 0;

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

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

    int cur = abs(h[i]-h[i-1])+minCosts[i-1];

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

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

    }

    minCosts[i] = cur;

  }

  cout << minCosts[n-1] << "\n";

  return 0;

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



#define fr first

#define sc second

#define OK puts("OK");

#define pb push_back

#define mk make_pair

#define ll long long

using namespace std;





const int inf = (int)1e9 + 7;

const int N = (int)1e5 + 7;



ll a,b;

ll ans;

ll p[N];



 main () {

    cin >> a >> b;



    if (b == 0) {

        cout << a * 1ll * a << endl;

        return 0;

    }

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

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

            p[j] ++;

    }

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

        p[i] += p[i - 1];



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

        ans += (a - i);

        ll x = i - b;



        ans += (i - (p[i] - p[x]) - b);

    }

    cout << ans << endl;

}


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

using namespace std;

const int MAXN = 101010;

typedef long long int LL;

int n, k;

int q[MAXN], p[MAXN];

long long int ans;

int main(){

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

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

        p[i] = n / i;

        q[i] = n % i;

    }

 

    if(k == 0){

        printf("%lld", (LL)n * (LL)n);

        return 0;

    }

 

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

        if(i <= k)

            continue;

        ans += (LL)(i - k) *  p[i];

        ans += q[i] >= k ? q[i] - k + 1 : 0;

    }

    printf("%lld", ans);

 

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



using namespace std;



int main(){

    int n, i, k , j;

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

    int height[n+5];

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

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

    }

    int ans = 1e9;

    int dp[n+5];

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

        dp[i] = 1e9;

    }

    dp[1] = 0;

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

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

            if(i > j) dp[i] = min(dp[i], dp[i-j] + abs(height[i] - height[i-j]));

        }

    }

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

    return 0;

}


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

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

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

//比如从k上面跳过来

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

//关键是你k不知道啊

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

//枚举

//dp[1] = 0

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

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

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

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

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

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <math.h>

#include <queue>

#include <stack>

#include <vector>

#include <algorithm>



using namespace std;



const int MAXN = 1e5;

int n,k;

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



int CHANGE(int i,int k)//

{

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

	{//从一开始选

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

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

		{

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

			{

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

			}

		}

		return min;

	}

	else

	{

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

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

		{

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

			{

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

			}

		}

		return min;

	}

}



int main()

{

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

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

	{

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

	}

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

	{

		if(i == 1)

		{

			dp[i] = 0;

		}

		else if(i == 2)

		{

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

		}

		else

		{

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

		}

	}

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

	return 0;

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

#include<cmath>

#include<cstring>

using namespace std;

int h[100005];

int dp[100005];

int main()

{

	int n,k;

	cin>>n>>k;

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

	cin>>h[i];

	memset(dp,0x3f3f3f,sizeof(dp));

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

	dp[1]=0;

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

		int d=0;

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

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

		}

	}	

	cout<<dp[n]<<endl;

}

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

using namespace std;

int main()

{

	int n,x;

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

	int a[n];

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

	{

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

	}

	long long b[n];

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

	{

		b[i]=0x3f3f3f3f;

	}

	b[0]=0;

	b[1]=abs(a[1]-a[0]);

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

	{

		for(int t=1;t<=x;t++)

		{

			if(i-t<0)break;

			b[i]=min(b[i-t]+abs(a[i]-a[i-t]),b[i]);

		}

	}

	printf("%lld",b[n-1]);

	return 0;

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



using namespace std;

 

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

 

#define nl '\n'

 

#define y1 aza_ibagaliev

 

#define f first

#define s second

	

#define ed end()

#define bg begin()

#define rbg rbegin()

 

#define rv reverse

#define mp make_pair

#define pb push_back

#define ppb pop_back

#define ppf pop_front

 

#define sz size()

#define all(x) x.bg, x.ed

 

#define pll pair < ll, ll >

#define pii pair < int, int >

 

#define sqr(x) ((x) * 1ll * (x))

#define sqrd(x) ((x) * 1.0 * (x))

 

#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

 

#define rnl cout << "----------------------------------------" << nl

 

#define bit __builtin_popcount

 

inline ll bip(ll x, ll n, ll mod){ll res=1;while(n){if(n & 1){res=(res*x)%mod;}x=(x*x)%mod;n>>=1;}return res;}

        	

const int ppr = 257;

const ll INF = 2e18;

const int inf = 2e9;

const int mod = 1e9 + 7;

const int N = 1e6 + 123;        	

const ld pi = 3.1741592653589793238462643;

 

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

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



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



main() {             	

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

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



//	srand(time(NULL));



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



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

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



		if(i == 1) continue;



		dp[i] = INF;

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

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

	}



	cout << dp[n];

             

    return 0;                                        

}

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

using namespace std;

using ll = long long;



int main() {

	int N;

	cin >> N;

	map<int, ll> A;

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

		int a;

		cin >> a;

		auto it = A.find(a);

		if (it == A.end()) {

			A.emplace(a, 1);

		} else {

			(it->second)++;

		}

	}

	ll S = 0;

	for (auto p : A) {

		S += p.first * p.second;

	}

	int Q;

	cin >> Q;

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

		int B, C;

		cin >> B >> C;

		if (A.find(B) != A.end()) {

			S += (C - B) * A.at(B);

			if (A.find(C) == A.end()) {

				A.emplace(C, A.at(B));

			} else {

				A.at(C) += A.at(B);

			}

			A.erase(B);

		}

		cout << S << endl;

	}

	return 0;

}


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



int main() {

	int N;

	scanf("%d", &N);

	int A[100000 + 1] = {0};

	long long S = 0;

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

		int a;

	 	scanf("%d", &a);

		A[a]++;

		S += a;

	}



	int Q;

	scanf("%d", &Q);

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

		int B, C;

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

		printf("%lld\n", S += (C - B) * A[B]);

		A[C] += A[B];

		A[B] = 0;

	}

	return 0;

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

#define ll long long

using namespace std;



int dp[100005], a[100005];

int n,k;



int solve(int n, int k)

{

    dp[0]=0;

    for(int i=0; i<n; 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]));

        }

    }

    return dp[n-1];



}

int main()

{

    cin>>n>>k;

    memset(dp, 1000000, sizeof(dp));

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

        cin>>a[i];

    cout<< solve(n,k) <<endl;

}




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

using namespace std;

const int INF = 1e9 + 5;



int main() {

    int n, k;

    cin>>n>>k;

    vector<int> stone(n);

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

        cin >> stone[i];



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



    cout << dp[n - 1];

    return 0;

}
// Slower C++ solution:
#define _CRT_SECURE_NO_WARNINGS

/*                   وتزودوا فإن خير الزاد التقوى                    */

/*       وما تدري نفس ماذا تکسب غدا وما تدري نفس باي ارض تموت      */

#include <bits/stdc++.h>

#include<unordered_map>

#include<iomanip>

#include<fstream>

using namespace std;

#include<iostream>

#define endl '\n'

#define ll long long

#define ull unsigned long long

#define dll double

#define PI acos(-1)

#define watch(x) cout<<#x<<" = { "<<x<<" }\n"

#define sz(n) n.size()

#define M_Sayed fast() 

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

#define allr(v) v.rbegin(),v.rend()

#define RT(v) return cout<<v,0

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

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

const double EPS = (1e-7);

ll Ceil(ll x, ll y) { return (x + y - 1) / y; }

void run() {

#ifndef ONLINE_JUDGE

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

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

#else

#endif

}

ll gcd(ll a, ll b) { return !b ? abs(a) : gcd(b, a % b); }

ll lcm(ll a, ll b) { return abs(a / gcd(a, b)) * b; }

ll power(ll x, ll y, ll mod) {

	if (y == 0) return 1;

	if (y == 1) return x % mod;

	ll r = power(x, y >> 1, mod);

	return (((r * r) % mod) * power(x, y & 1, mod)) % mod;

}

void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

ll n, m, k,su,cnt;

ll vis[100009];

vector<ll>v;

ll Jum(int x) {

	if (x+1 == n)

		return 0;

	ll &ret = vis[x];

	if (~ret)return ret;

	 ret = abs(v[x] - v[x + 1])+Jum(x + 1) ;

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

		if(i+x<n)ret = min(ret,Jum(x + i) + abs(v[x] - v[x + i]));

	}

	return ret;

}

int main()

{

	//run();

	M_Sayed;

	cin >> n>>k ;

	memset(vis, -1, sizeof vis);

	v.resize(n);

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

		cin >> v[i];

	}

	RT(Jum(0));

}

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

using namespace std;

int h[100001];

int dp[100001];

int n,k;

int solve(int stone)

{

    if(stone==n) return 0;

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

    int cost=1<<30;

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

    cost=min( cost,abs(h[stone]-h[stone+i])+solve(stone+i) );



    return dp[stone]=cost;

}



int main()

{

    int i;

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



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

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



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

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





    return 0;

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

#include <iostream>

#include <algorithm>



using namespace std;



vector<vector<int> > G;



vector<bool> used;



int rec(int pos)

{

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

    

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

    {

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

        {

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

        }

    }

    

    used[pos] = false;

    

    return ret;

}



int main()

{

    int N, A, B;

    

    while(true)

    {

        scanf("%d", &N);

        

        if(N == 0) { break; }



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

        

        used = vector<bool>(100);

    

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

        {

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

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

        

            G[A].push_back(B);

            G[B].push_back(A);

        }

        

        int nodes = 0;

        

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

        {

            if(G[i].size())

            {

                nodes++;

            }

        }

    

        int ret = 0;

    

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

        {

            if(G[i].size())

            {

                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.999191562292758x):
#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;



int arr[100100], dp[100100];



int main() {

  int n, k;

  cin >> n >> k;

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



  dp[0] = 0;

  for (int i = 1; i < n; ++i) dp[i] = 2e9;



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

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

      if ( pos - step < 0 ) break;

      dp[pos] = min( dp[pos], dp[pos - step] + abs(arr[pos] - arr[pos - step]) );

    }

  }

  

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

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.2226541683562235x):
#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 n,k,dp[100009],a[100009],mx=1e9+8;

int bt(int x)

{

    if(x==0)return 0;

    if(x==1)return abs(a[x]-a[x-1]);

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

    dp[x]=mx;

    for(int i=1;i<=k&&x-i>=0;i++)

    {

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

    }

    return dp[x];

}

int main()

{

    cin>>n>>k;

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

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

    cout<<bt(n-1);

}


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

using namespace std;

int n,k,dp[100009],a[100009],mx=1e9+8;

int main()

{

    cin>>n>>k;

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

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

    dp[0]=0;

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

    {

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

        {

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

        }

    }

    cout<<dp[n-1];

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

using namespace std;

#define ll long long

#define pb push_back

#define mp make_pair



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



int main()

{

    cin>>n>>k;

    for(ll i=0;i<100005;i++) dp[i] = LONG_LONG_MAX;

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

    dp[0] = 0;

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

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

    {

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

        {

            if(i-j>=0)

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

        }

    }

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

}

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

using namespace std;

#define ll long long

#define pb push_back

#define mp make_pair

#define ff first

#define ss second

#define rep(i,a,b) for(ll i=a;i<b;i++)

#define repv(i,a,b) for(ll i=b-1;i>=a;i--)

#define MAXN 100005

#define endl "\n"



ll power(ll x,ll y){ll res=1; while(y>0){if(y&1) res=res*x;y=y>>1;x=x*x;}return res;}



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



int main()

{

	ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    cin>>n>>k;

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

    rep(i,1,n+1) dp[i]=INT_MAX;

    dp[1]=0;

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

    {

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

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

    }

    cout<<dp[n]<<endl;

}
// Slower C++ solution:


#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <map>

#include <cmath>

#include <queue>

#include <set>

#include <ctime>

#define rep(i,j,k) for(int i = j; i <= k; i++)

#define dow(i,j,k) for(int i = j; i >= k; i--)

#define ez(i,x) for(int i = h[x]; i; i = e[i].next)

#define fi first

#define se second

#define MS(x) memset(x, 0, sizeof(x))

using namespace std;





int main() {

    int n;

	ios::sync_with_stdio(0);

	cin >> n;

	map<int,int> m;

	long long sum = 0;

	rep(i,1,n) {

		int x;

		cin >> x;

		m[x]++;

		sum += x;

	}

	int q;

	cin >> q;

	while (q--) {

		int x, y;

		cin >> x >> y;

		sum = sum - 1ll * m[x] * x + m[x] * 1ll * y;

		m[y] += m[x];

		m[x] = 0;

		cout << sum << "\n";

	}

}

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

#include<algorithm>

#include<cstring>



using namespace std;



int num[100100];



int main()

{

    int n,k,i;

    int a,b,q;

    long long t;

    long long total=0;

    scanf("%d",&n);

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

    {

        scanf("%d",&a);

        total+=a;

        num[a]++;

    }

    scanf("%d",&q);

    while(q--)

    {

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

        t=num[a];

        num[a]=0;

        num[b]+=t;

        total+=t*b-t*a;

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

    }

    return 0;

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



#include <iostream>

#define pb push_back

#define sort_incr(v) sort(v.begin(),v.end());

#define sort_decr(v) {sort(v.begin(),v.end()); reverse(v.begin(),v.end());}

#define take_input(v,n) for(ll i=0,temp;i<n;i++){cin>>temp;v.pb(temp);}

#define fastio {ios_base::sync_with_stdio(false);    cin.tie(NULL);}

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



typedef long long ll;

using namespace std; 



int main() 

{

    fastio;

    ll n,temp,su=0;

    cin>>n;

    vector<ll> v;

    int co[100004]={0};

    // take_input(v,n);

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

    {

        cin>>temp;

        co[temp]++;

        su=su+temp;

    }

    ll q ;

    cin>>q;

    while(q--)

    {

        ll a,b;

        cin>>a>>b;

        su=su+(b-a)*co[a];

        co[b]+=co[a];

        co[a]=0;

        

        cout<<su<<"\n";

        

    }

    

    return 0; 

} 

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


#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <map>

#include <cmath>

#include <queue>

#include <set>

#include <ctime>

#define rep(i,j,k) for(int i = j; i <= k; i++)

#define dow(i,j,k) for(int i = j; i >= k; i--)

#define ez(i,x) for(int i = h[x]; i; i = e[i].next)

#define fi first

#define se second

#define MS(x) memset(x, 0, sizeof(x))

using namespace std;





int main() {

    int n;

	ios::sync_with_stdio(0);

	cin >> n;

	map<int,int> m;

	long long sum = 0;

	rep(i,1,n) {

		int x;

		cin >> x;

		m[x]++;

		sum += x;

	}

	int q;

	cin >> q;

	while (q--) {

		int x, y;

		cin >> x >> y;

		sum = sum - 1ll * m[x] * x + m[x] * 1ll * y;

		m[y] += m[x];

		m[x] = 0;

		cout << sum << "\n";

	}

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

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

		}

	}

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

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.380337537828405x):
/**

     **author : _KMS_

     **created : 28-03-2020

**/

#include<bits/stdc++.h>

using namespace std;

const long long M =2e5+10,MOD=998244353;

typedef long long ll;

int arr[M];

int dp[M];

int main() {

   

  ios::sync_with_stdio(false);

  cin.tie(0);

  int n,k;

  cin>>n>>k;

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

  cin>>arr[i];

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

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

 arr[0]=arr[1];

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

  {  int temp=k;

     int in=i-1;

     while(temp>0&&in>0){

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

    temp--;

    in--;

  }

  }

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



  return 0;

}