stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#define _CRT_SECURE_NO_WARNINGS

#include<bits/stdc++.h>

#include<unordered_map>

#include<unordered_set>	

using namespace std;

typedef long long ll;

#define bay_bay return 0;

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

#define for1(n) for(int i=1;i<=n;i+=3)

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

#define sz(v) v.size()

#define endl "\n"

constexpr auto EPS = 1e-9;

#define ff fflush(stdout);

const int mod = 1000000007LL;

clock_t T;

#define ctime cerr << "Time : " << double(clock() - T) / CLOCKS_PER_SEC << endl

void GOAT()

{

	std::ios_base::sync_with_stdio(0);

	cin.tie(NULL);

	cout.tie(NULL);

#ifndef ONLINE_JUDGE

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

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

#else

#endif

}

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



int main()

{

	//GOAT();

	cin >> n >> k;

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

		cin >> arr[i];

	memset(dp, -1, sizeof dp);

	dp[1] = 0;

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

	{

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

		{

			if (i + j <= n)

			{

				ll ch = dp[i] + abs(arr[i] - arr[i + j]);

				if (ch < dp[i + j] || dp[i + j] == -1)dp[i + j] = ch;

			}

		}

	}

	cout << dp[n] << endl;

}

// Optimized solution to the same problem (faster):
/******

author :- Mahmoud Tarek.

*******/



#include<bits/stdc++.h>



using namespace std ;



#define rg register

#define dbg(v) cerr << #v << " " << v ;

typedef long long ll ;



int n, k;

vector<int> a ;

int mx = 0 ;

int mem[100002] ;



int solve(int i){

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

int & ret = mem[i];

if(~ret) return ret ;

ret = mx ;

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

    if(i + j < n){

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

    }

}

return ret ;

}



int main() {

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

     cin >> n >> k ;

     a.resize(n) ;



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

        cin >> a[i] ;

        if(i >= 1){

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

        }

     }



     if(mx == 0) mx = a[0] ;





     memset(mem, -1, sizeof mem) ;



     cout << solve(0);

}



/*

  Empty set of troubles.

*/


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

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

#define ll long long

const ll INF = 1e18;



int main(void)

{

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

    cin >> n >> m;

    vector<ll> a(200000,0);

    rep(i,m){

        ll a, b;

        cin >> a >> b;

        l = max(l, a);

        r = min(r, b);

    }

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

    return 0;

}

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

using namespace std;

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



int main(void)

{

    int n, m, l=1, r;

    cin >> n >> m;

  	r = n;

    rep(i,m){

        int a, b;

        cin >> a >> b;

        l = max(l, a);

        r = min(r, b);

    }

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

    return 0;

}

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

using namespace std;



int main()

{

    int N, M;

    cin >> N >> M;

    int LMax = 1;

    int RMin = N;

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

    {

        int L;

        int R;

        cin >> L >> R;

        LMax = max(LMax, L);

        RMin = min(RMin, R);

    }

    if(RMin + 1 >= LMax)

        cout << RMin - LMax + 1 << endl;

    else

        cout << "0" << endl;

    return 0;

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

#include <algorithm>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

using namespace std;



int main()

{

    long long n;

    scanf("%lld",&n);

    long long i,sum=1;

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

    {

        sum*=i;

        sum%=1000000007;

    }

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

    return 0;

}


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

#include <algorithm>

using namespace std;



int main()

{

	int n,i;

	long long sum=1;

	scanf("%d",&n);

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

	{

		sum*=i;

		sum%=(1000000000+7);

	}

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

	return 0;

}


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

typedef long long ll;

#define INF 1LL<<62

#define inf 1000000007



int main() {

	ll n,m;

	cin>>n>>m;

	bool ac[100010]={false};

	ll wa[100010]={};

	for(ll i=0;i<m;i++){

		ll now;string s;

		cin>>now>>s;

		now--;

		if(s=="WA"){

			if(ac[now]==false){

				wa[now]++;

			}

		}

		else{

			ac[now]=true;

		}

	}

	ll accnt=0;ll wacnt=0;

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

		if(ac[i]){

			accnt++;

			wacnt+=wa[i];

		}

	}

	cout << accnt<<" "<<wacnt;

	// your code goes here

	return 0;

}

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

using namespace std;

typedef long long ll;

#define INF 1LL<<62

#define inf 1000000007

 	bool ac[100010]={};

	ll wa[100010]={};

int main() {

	ll n,k;

	cin>>n>>k;



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

		ll x;string s;

		cin>>x>>s;x--;

		if(s=="AC"){

			ac[x]=true;

		}

		else{

			if(ac[x]!=true){

				wa[x]++;

			}

		}

	}

		ll cnt1=0;

		ll cnt2=0;

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

			if(ac[i]){

				cnt1++;

				cnt2+=wa[i];

			}

		}

		cout << cnt1<<" "<<cnt2;	

	// your code goes here

	return 0;

}

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

#include <vector>

using namespace std;

int main ()

{

	int n, m, acc=0, pen=0; cin>>n>>m;

	bool test[n+1]={false};

	int arr[n+1]={0};

	int p[m];

	string s[m];

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

	{

		cin>>p[i];

		cin>>s[i];

		if (test [p[i]]==false && s[i]=="AC")

		{

			test[p[i]]=true;

			acc++;

			pen+=arr[p[i]];

		}

		if (test[p[i]]==false && s[i]=="WA")

		{

			arr[p[i]]++;

		}

	}

	cout<<acc<<endl<<pen<<endl;

	return 0;

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

#include<string>

using namespace std;

int main(){

	int k;

	string s;

	cin>>k>>s;

	if(s.length()<=k) cout<<s<<endl;

	else{

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

			cout<<s[i];

		}

		cout<<"...";

	}

	return 0;

} 

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

#include <string.h>

int main(){

	int k;

	scanf("%d",&k);

	char s[100];

	scanf("%s",&s);

	int lol = strlen(s);

	s[k] = '\0';

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

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

	}

	if(k<lol){

		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,k;

int dp[100005],num[100005];

int main() {

	cin.tie(),cout.tie();

	memset(dp,233333,sizeof(dp));

	cin>>n>>k;

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

	dp[0]=0;

	dp[1]=0;

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

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

			int add=fabs(num[i]-num[j]);

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

		}

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

	}

	cout<<dp[n]<<endl;

	return 0;

} 

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

using namespace std;

typedef long long ll;

const ll inf=1e9;

ll n,k,num[2000005],dp[2000005];

inline ll smax(ll x,ll y) {return x>y?x:y;}

inline ll smin(ll x,ll y) {return x<y?x:y;}

inline ll sabs(ll x) {return x>0?x:-x;}

int main() {

	cin>>n>>k;

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

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

	dp[1]=0;

	dp[2]=dp[1]+sabs(num[1]-num[2]);

//	cout<<smax(1,10000)<<' '<<smin(1,10000)<<' '<<sabs(5-100);

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

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

			dp[i]=smin(dp[i],dp[j]+abs(num[i]-num[j]));

	

//	for (int i=1;i<=n;i++) cout<<dp[i]<<' ';

//	cout<<endl;

	cout<<dp[n]<<endl;

	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;



int n,m;

int l[1000000];

int dp[1000000];

main()

{

    cin>>n>>m;

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

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

        cin>>l[i];

    }

    dp[1]=0;

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

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

        for(int j=i-1;j>=i-m;j--){

            if(j<0)break;;

            dp[i]=min(dp[i],dp[j]+abs(l[j]-l[i]));//cout<<j<<" ";

        }//cout<<dp[i];

        //cout<<"\n";

    }

    cout<<dp[n];

}


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

} 

// 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 ll long long int

#define M 1000000007

#define mod 998244353

#define mp(x,y) make_pair(x,y)

#define pb(x) push_back(x)

#define pi pair<ll,ll>

using namespace std;

const ll N=1e5+10;



ll n,k;

ll ar[N];

ll dp[N];



ll func(ll i)

{

    if(i>=n){return(INT_MAX);}

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

    if(dp[i]==-1)

    {

        ll ans=INT_MAX;

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

        {

            ans=min(ans,func(i+j+1)+abs(ar[i]-ar[i+j+1]));

        }

        dp[i]=ans;

    }

    return(dp[i]);

}



int main()

{

	ios_base::sync_with_stdio(false);

	cin.tie(NULL);

	cout.tie(NULL);



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

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



	cin>>n>>k;

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

    {

        cin>>ar[i];

    }

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

    cout<<func(0);



	return(0);

}


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

#define ll long long int

#define M 1000000007

#define mod 998244353

#define mp(x,y) make_pair(x,y)

#define pb(x) push_back(x)

#define pi pair<ll,ll>

using namespace std;

const ll N=100010;



vector<ll> ar;

ll k;

ll dp[N];

ll func(ll idx)

{

    if(idx<0){return INT_MAX;}

    if(idx==0){return 0;}

    if(dp[idx]==-1)

    {

        ll ans=INT_MAX;

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

        {

            if(idx-i>=0)

            {ans=min(ans,func(idx-i)+abs(ar[idx]-ar[idx-i]));}

        }

        dp[idx]=ans;

    }

    return dp[idx];

}



int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    cout.tie(NULL);



    ll n;

    cin>>n>>k;

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

    {

        ll x;

        cin>>x;

        ar.pb(x);

        dp[i]=-1;

    }



    ll ans=func(n-1);



    cout<<ans<<endl;



    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>

#include <ext/numeric>



using namespace std;

using namespace __gnu_cxx;



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

#define endl "\n"

#define pb push_back

#define F first

#define S second

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

#define isOdd(n)    (n&1)

#define LLMAX LLONG_MAX

#define LLMIN LLONG_MIN

#define IMN INT_MIN

#define IMX INT_MAX

#define pow(n, m) power((ll)n, (ll)m)

#define numOfDigits(n)  ((n)? (ll)(log10(n)+1) : 1)

#define mem(x, val)    memset(x, val, sizeof(x))



typedef long long ll;

typedef long double ld;

typedef double dd;

typedef string str;

typedef pair<int, int> pii;





vector<int> v;

int dp[(int)1e5];

int n, k;

int jump(int i){

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

    if(i>=n) return 1e9;



    int &ret = dp[i];



    if(~ret) return ret;



    int cnt = 1e9;

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

        if(i+j<n) cnt = min(cnt, abs(v[i] - v[i+j]) + jump(i+j));

    }



    return ret = cnt;

}

int main()

{

    THINK_TWICE_CODE_ONCE

    //freopen("test cases\\.txt", "r", stdin) ;

    cin>>n>>k;

    v.resize(n);

    for(int &i: v) cin>>i;

    mem(dp, -1);

    cout<<jump(0);

    return 0;

}










// Optimized solution to the same problem (faster):
#define _CRT_SECURE_NO_WARNINGS

#include<iostream>

#include<functional>

#include <bitset>

#include<algorithm>

#include<fstream>

#include<string>

#include <cstring>

#include<stdio.h>

#include<iomanip>

#include<sstream>

#include<cmath>

#include<vector>

#include<assert.h>

#include<queue>

#include<deque>

#include<stack>

#include<set>

#include<map>

// never lose hope ..

typedef unsigned long long ull;

typedef long long ll;

typedef long double ld;

#define eps 1e-8

using namespace std;

double const  PI = 3.141592653;

const int OO = 1000000000 + 9;



void fast() {

	ios_base::sync_with_stdio(0);

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

}





int main()

{

	fast();



	int n, k;

	cin >> n >> k;

	vector<int>v(n + 1, 0), dp(n + 1, OO);

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

		cin >> v[i];

	}

	dp[1] = 0;

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

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

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

		}

	}

	cout << 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<iostream> 

#include<cstring>

using namespace std;

const int maxn=1e5+10;

const int inf=0x3f3f3f3f;

int main()

{

	int a[maxn]; 

	int dp[maxn];

	int n,k;

	cin>>n>>k;

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

	 cin>>a[i];

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

	dp[1]=0;

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

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

		{

			if(i-j<1)

				break;

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

		}			

	cout<<dp[n]<<endl;

	return 0;

}

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

using namespace std;

const int maxn=100010;

const int inf=0x3f3f3f3f;

int dp[maxn];

int a[maxn];

int main()

{

	int n,k;

	cin>>n>>k;

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

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

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

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

			if(i-j<1)break;

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

		}

	}

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





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

#include <cstdio>

#include <cstring>

using namespace std;

int res[100005] = {0};

int N,d = 0;

long long sum = 0;

int main()

{



     while(~scanf("%d",&N))

    {

     sum = 0;

     memset(res,0,sizeof(res));

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

     {

        scanf("%d",&d);

        res[d] ++;

        sum+= d;

     }

     int Q;

     scanf("%d",&Q);

     int y=0,x=0;

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

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

        sum += (x-y)*res[y];

        res[x] += res[y];

        res[y] = 0;

        cout<<sum<<endl;

     }

     }

    return 0;

}


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

	}

}

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

using namespace std;

#define ll long long

#include <string>

const int mxN=1e5;

const int maxN=5e3;

#define ld long double

#define pb push_back

#define mp make_pair

#define ins insert

#define vi vector<int>



int main()

{

    int n;

    cin >> n;

    int cnt[100000]={};

    ll s=0;

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

    {

        int x;

        cin >> x;

        cnt[x-1]++;

        s+=x;

    }

    int q;

    cin >> q;

    while(q--)

    {

        int b,c;

        cin >> b >> c;

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

        cnt[c-1]+=cnt[b-1];

        cnt[b-1]=0;

        cout << s << "\n";

    }

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

 

#define ull unsigned long long

#define ll long long

#define pb push_back

#define mp make_pair

#define y1 my_y1

#define fi first

#define se second

#define lcm mylcm

 

using namespace std;

 

const ll mod = 998244353;

const ll inf = 2e9;

const int N = 1e5 + 5;



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



int main () {

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

    cin.tie(NULL);

	cout.tie(NULL);

	ios_base::sync_with_stdio(false);

	cin >> n >> k;

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

		cin >> h[i];

		dp[i] = inf;

	}

	dp[1] = 0;

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

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

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

		}

	}

	cout << dp[n];

	return 0;

}

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

}

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





}