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

#include<algorithm>

#include<vector>

#include<cstdio>

using namespace std;



static const int Max = 100000;



long long gcd(long long a, long long b){

    long long tmp;

    while( b != 0){

        tmp = b;

        b = a % b;

        a = tmp;

    }

    return a;

}



int main(){

    int n;

    cin >> n;

    vector<long long> v;

    long long l[Max] = {0}, r[Max] = {0};

    long long t, ans = 0;

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

        cin >> t;

        v.push_back(t);

    }

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

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

        if(i == 1){

            l[i] = v[i-1];

            r[n-1-i] = v[n-i];

        }

        else{

            l[i] = gcd(l[i-1], v[i-1]);

            r[n-1-i] = gcd(r[n-i], v[n-i]);

        }

    }

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

        if(i == 0) ans = r[i];

        else if(i == n-1){

            if(l[i] > ans) ans = l[i];

        }else{

            if(ans < gcd(l[i], r[i])){

                ans = gcd(l[i], r[i]);

            }

        }

    }

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

    return 0;

}

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

using namespace std;

typedef long long ll;



int main(){

    int N; cin >> N;

    vector<ll> A(N);

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

    vector<ll> left(N), right(N);

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

        if(i == 1){

            left[i] = A[0];

            right[N-i-1] = A[N-1];

        }

        else{

            left[i] = __gcd(left[i-1], A[i-1]);

            right[N-i-1] = __gcd(right[N-1 -(i-1)], A[N-i]);

        }

    }

    ll MAX = 0;

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

        if(i == 0) MAX = max(right[i],MAX);

        else if(i == N - 1) MAX = max(left[i],MAX);

        else MAX = max(MAX, __gcd(left[i],right[i]));

    }

    cout << MAX << endl; 

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

const int maxn=2e5+5;

int a[maxn];

int main(){

	int n;

	cin>>n;

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

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

	}

	int ans=-maxn;

	for(int i=1;i*i<=a[0];i++){

		int x=0;

		if(a[0]%i!=0) continue;

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

			if(a[j]%i!=0)

			x++;

			if(x==2)

			break;

		}

		if(x<2)

		ans=max(ans,i);

		int ii=a[0]/i;

		x=0;

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

			if(a[j]%ii!=0)

			x++;

			if(x==2)

			break;

		}

		if(x<2)

		ans=max(ans,ii);

	}

	for(int i=1;i*i<=a[1];i++){

		int x=0;

		if(a[1]%i!=0) continue;

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

			if(a[j]%i!=0)

			x++;

			if(x==2)

			break;

		}

		if(x<2)

		ans=max(ans,i);

		int ii=a[1]/i;

		x=0;

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

			if(a[j]%ii!=0)

			x++;

			if(x==2)

			break;

		}

		if(x<2)

		ans=max(ans,ii);

	}

	cout<<ans;

}

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

using namespace std;

const int maxn=2e5+5;

int a[maxn],l[maxn],r[maxn]; 

int gcd(int a,int b){

	int t;

	if(a<b){

		t=a;

		a=b;

		b=t;

	}

	if(b==0)

	return a;

	for(;;){

		int tmp;

		tmp=b;

		b=a%b;

		a=tmp;

		if(b==0)

		return a;

	}

}

int main(){

	int n;

	cin>>n;

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

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

	}

	

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

			l[i]=gcd(l[i-1],a[i]);

			}

	    for(int i=n;i>=1;i--){

	    	r[i]=gcd(r[i+1],a[i]);

		}

			int ans=0;

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

				ans=max(ans,gcd(l[i-1],r[i+1]));

				

			}

		

	   //存储下来 不然会TLE 

	cout<<ans;

	return 0;

} 

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include "bits/stdc++.h"

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

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

#define iostreamBooster() do{ cin.tie(nullptr); ios_base::sync_with_stdio(false); }while(0)

using namespace std;

typedef int64_t i64;

typedef pair<int,int> pii;

template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}

template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}

constexpr int INF = 0x3f3f3f3f;



void storeDivisor(vector<int> &dst, int n)

{

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

    if (n % i == 0) {

      dst.push_back(i);

      dst.push_back(n / i);

    }

  }

  return;

}



signed main()

{

  int N;

  int a[100010];



  cin >> N;

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



  vector<int> divisors;

  storeDivisor(divisors, a[0]);

  storeDivisor(divisors, a[1]);

  sort(ALL(divisors));

  divisors.erase(unique(ALL(divisors)), divisors.end());





  i64 ans = 1;



  for (int d : divisors) {

    const int cnt = count_if(a, a+N, [d](int a){ return a % d == 0; });

    if (cnt >= N-1) chmax(ans, d);

  }



  cout << ans << endl;



  return 0;

}




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

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

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

#define iostreamBooster() do{ cin.tie(nullptr); ios_base::sync_with_stdio(false); }while(0)

using namespace std;

typedef int64_t i64;

typedef pair<int,int> pii;

template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}

template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}

constexpr int INF = 0x3f3f3f3f;



template<class Monoid>

struct SegTree {

  using F = function<Monoid(Monoid, Monoid)>;



  int sz;

  vector<Monoid> u;

  const F f;

  const Monoid M;



  SegTree(int n, const F f, const Monoid &M)

    : f(f), M(M)

  {

    for (sz = 1; sz < n; sz <<= 1);

    u.assign(sz * 2, M);

  }



  void set(int i, const Monoid &v) {

    u[i + sz] = v;

  }



  void build() {

    for (int i = sz-1; i > 0; --i) u[i] = calc(i);

  }



  void update(int i, const Monoid &v) {

    u[i += sz] = v;

    while(i >>= 1) u[i] = calc(i);

  }



  Monoid query(int a, int b) const {

    Monoid L = M, R = M;

    for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {

      if (a & 1) L = f(L, u[a++]);

      if (b & 1) R = f(u[--b], R);

    }

    return f(L, R);

  }



  Monoid calc(int i) const {

    return f(u[2 * i + 0], u[2 * i + 1]);

  }



  const Monoid& operator[] (int i) const {

    return u[i + sz];

  }

};



signed main()

{

  int N; cin >> N;



  SegTree<int> seg(

      N+1,

      [](int a, int b) { return __gcd(a,b); },

      0);



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

    int a; cin >> a;

    seg.set(i, a);

  }



  seg.build();



  int ans = 1;

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

    chmax(ans, __gcd(seg.query(0, i), seg.query(i+1, N+1)));

  }



  cout << ans << endl;



  return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;



#define llong long long int

#define ldouble long double

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

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

#define fore(i,a) for (auto &i : a)

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

#define stl_rep(itr, x) for (auto itr = x.begin(); itr != x.end(); ++itr)

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

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



const static int mod = 1000000000 + 7;

const static int inf = INT_MAX / 2;

const static llong INF = LLONG_MAX / 2;

const static double eps = 1e-10;

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

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



signed main (int argc, char *argv[]) {

    int n;

    cin >> n;

    vector<int> A(n);

    rep(i, n) cin >> A[i];



    priority_queue<int> divisers;

    for (int i = 1; i * i <= A[0]; ++i) {

        if (A[0] % i == 0) divisers.push(i), divisers.push(A[0] / i);

    }

    for (int i = 1; i * i <= A[1]; ++i) {

        if (A[1] % i == 0) divisers.push(i), divisers.push(A[1] / i);

    }

    

    int divi;

    while(! divisers.empty()){

        divi = divisers.top();

        int cnt = 0;

        rep(i, n) {

            if (A[i] % divi) ++cnt;

        }

        if (cnt == 0 || cnt == 1) break;

        divisers.pop(); 

    }



    cout << divi << endl;

    

    return 0;

}

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



using namespace std;



#define llong long long int

#define ldouble long double

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

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

#define fore(i,a) for (auto &i : a)

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

#define stl_rep(itr, x) for (auto itr = x.begin(); itr != x.end(); ++itr)

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

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



const static int mod = 1000000000 + 7;

const static int inf = INT_MAX / 2;

const static llong INF = LLONG_MAX / 2;

const static double eps = 1e-10;

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

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



template<typename T> T my_gcd(T a, T b) {

    return (a ? my_gcd(b % a, a) : b);

}



signed main (int argc, char *argv[]) {

    int n;

    cin >> n;

    vector<int> A(n);

    rep(i, n) cin >> A[i];



    vector<int> gcd_from_left, gcd_from_right;

    gcd_from_left.push_back(A[0]), gcd_from_right.push_back(A[n - 1]);

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

        gcd_from_left.push_back(my_gcd(A[i], gcd_from_left[i - 1]));

        gcd_from_right.push_back(my_gcd(A[n - 1 - i], gcd_from_right[i - 1]));

    }



    priority_queue<int> gcds;

    int left = -1, right = n - 2;

    rep(_, n + 1) {

        if (left == -1) {

            gcds.push(gcd_from_right[right]);

        } else if (right == -1) {

            gcds.push(gcd_from_left[left]);

        } else {

            gcds.push(my_gcd(gcd_from_left[left], gcd_from_right[right]));

        }

        ++left, --right;

    }



    cout << gcds.top() << endl;

    

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

int N;

vector<int> A(100010);



int GCD(int a, int b) {

    if(a == 0) {

        return b; 

    }else if(b == 0) {

        return a;

    }else {

        int r, tmp;

        if(a < b) {

            tmp = a;

            a = b;

            b = tmp;

        }



        r = a % b;

        while(r != 0) {

            a = b;

            b = r;

            r = a % b;

        }

        return b;

    }

}



vector<int> M(100010, 0);

vector<int> L(100010, 0);

vector<int> R(100010, 0);



int main() {

    cin >> N;

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

        cin >> A.at(i);

    }



    L.at(0) = 0; R.at(N+1) = 0;



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

        L.at(i+1) = GCD(L.at(i), A.at(i));

    }



    for(int i = N; i > 0; --i) {

        R.at(i) = GCD(R.at(i+1), A.at(i));

    }



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

        cout << L.at(i) << " " << R.at(i+1) << endl;

    }*/



    int max = 0;



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

        M.at(i) = GCD(L.at(i), R.at(i+1));

        if(max < M.at(i)) max = M.at(i);

    }



    cout << max << endl;



}

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

using namespace std;



// GCD

int gcd(int a, int b) {

    if(a == 0) return b;

    if(b == 0) return a;

    if(a < b) {

        int tmp = a;

        a = b;

        b = tmp;

    }

    int r = a % b;



    while(r > 0) {

        a = b;

        b = r;

        r = a % b;

    }

    return b;

}



int n;

vector<int> l(100010);

vector<int> r(100010);

vector<int> mgcd(100010);



int main() {

    cin >> n;

    vector<int> a(n+1, 0);

    for(int i = 0; i < n; ++i) cin >> a.at(i);



    l.at(0) = 0; r.at(n+1) = 0;

    for(int i = 0; i < n; ++i) l.at(i+1) = gcd(l.at(i), a.at(i));

    for(int i = n; i > 0; --i) r.at(i) = gcd(r.at(i+1), a.at(i));



    int maxgcd = 0;



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

        mgcd.at(i) = gcd(l.at(i), r.at(i+1));

        maxgcd = max(maxgcd, mgcd.at(i));

    }



    cout << maxgcd << endl;





}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



int main() {

  int64_t b;



  while (cin >> b, b) {

    for (int64_t d = sqrt(2 * b + b); d > 0; --d) {

      int64_t a = (2 * b + d - d * d) / (2 * d);

      if (a <= 0 || b < a) continue;

      if ((a + d) * (a + d - 1) - a * (a - 1) == 2 * b) {

        cout << a << " " << d << endl;

        break;

      }

    }

  }

}




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

using namespace std;



int main() {

  int64_t b;



  while (cin >> b, b) {

    for (int64_t d = sqrt(2 * b); d > 0; --d) {

      int64_t a = (2 * b + d - d * d) / (2 * d);

      if (a <= 0 || b < a) continue;

      if ((a + d) * (a + d - 1) - a * (a - 1) == 2 * b) {

        cout << a << " " << d << endl;

        break;

      }

    }

  }

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define INF 1e9

using namespace std;



int fir;



bool solve(long long n,long long m){//nのm分割

    if(n%m!=0 && m%2==1)return false;

    if(m%2==0 && (2*n)%m!=0)return false;

    if((m%2)==1){

        if(((n/m)-((m-1)/2))>=1){

            fir=n/m-(m-1)/2;

            return true;

        }

        else{

            return false;

        }

    }

    else{

        if(((2*n)/m)%2==1){

            fir=(2*n/m-m+1)/2;

            return true;

        }

        else return false;

    }

}



signed main(){

    ios::sync_with_stdio(false);

    cin.tie(0);



    while(1){

        int a;

        cin>>a;

        if(a==0)break;

        fir=a;

        int ans=1;

        for(long long i=1;i*i/2<=a;i++){

            if(solve(a,i)){

                    ans=i;

            }

        }

        cout<<fir<<" "<<ans<<endl;

    }

}


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

#define INF 1e18

#define int long long

#define Rep(i, a, n) for (int i = (a); i < (n); i++)

#define rep(i, n) Rep(i, 0, n)

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

using namespace std;

typedef pair<int, int> P;

typedef pair<int, P> PP;

const int mod = 1000000007;



signed main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);



    int b;

    while (cin >> b, b)

    {

        int ans1, ans2;

        for (int i = 1; i * (i + 1) / 2 <= b; i++)

        {

            //s * i + i * (i - 1) / 2 = b

            if ((2 * b - i * (i - 1)) % (2 * i) == 0)

            {

                ans1 = ((2 * b - i * (i - 1)) / (2 * i));

                ans2 = i;

            }

        }

        cout << ans1 << " " << ans2 << endl;

    }

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



#define FOR(i,a,b) for(long long i=(a);i<(b);++i)

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

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



using namespace std;



int main(){

  long long b;

  while(true){

    cin >> b;

    if(b == 0) break;

    pair<int,int> ans;

    FOR(n,1, sqrt(2*b) ){

      //b = n(2a+n-1)/2

      //2b/n = 2a + n - 1

      // (2b/n - n + 1)/2 = a

      //cout << " n :" << n;

      long long a = ((2 * b) / n - n + 1) / 2;

      //cout << " a: " << a << endl;

      if((2 * b == n * (2*a + n - 1))  ){

        //cout << a << ' ' << a + n - 1 << endl;

        ans.first = a;

        ans.second = n;

      }

    }

    cout << ans.first << ' ' << ans.second << endl;

  }

  return 0;

}




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

using namespace std;



//repetition

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

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



//container util

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



//typedef

typedef long long ll;

typedef vector<int> VI;

typedef vector<VI> VVI;

typedef vector<ll> VLL;

typedef vector<VLL> VVLL;

typedef vector<string> VS;

typedef pair<int, int> PII;

typedef pair<ll, ll> PLL;



//const value

//const ll MOD = 1e9 + 7;

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

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



//conversion

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}

inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}

template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}





void solve(ll b){

  int s = 0;

  int e = 0;

  for(ll n = 1; n*n < 2*b; n++){

    if( (2 * b  - n * (n-1)) % (2*n) == 0){

      s = (2 * b  - n * (n-1)) / (2*n);

      e = n;

    }

  }

  cout << s << " " << e << endl;

  return;

}



int main(){

  ios::sync_with_stdio(false);

  cin.tie(0);

  ll b;

  while(true){

    cin >> b;

    if(b == 0) break;

    solve(b);

  }

  return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <vector>

#include <iostream>

#include <algorithm>

#include <string>

using namespace std;



int main()

{

	int n = 0;

	int k = 0;

	string str;

	int origin = 0;

	cin >> n;

	cin >> k;

	cin >> str;

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

		if (str[i] == str[i + 1]) { ++origin; }

	}

	cout << min(origin + 2 * k, n - 1);

}

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

#include<cstdlib>

#include<cstdio>

#include<cmath>

#define N 200020

using namespace std;

int n,k,cnt;

char ch[N];

int main()

{

	scanf("%d%d%s",&n,&k,ch+1);

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

	{

		int j=i;

		while(ch[j+1]==ch[i])j++;

		cnt++;i=j;

	}

	cnt=max(1,cnt-2*k);

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

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
///By Stephan Ramirez dsramirezc@unal.edu.co

#include<bits/stdc++.h>

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

#define ll long long

#define N 100005

using namespace std;

int n,k;

char s[N];

int main(){

	#ifdef LOCAL

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

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

	#endif

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

    scanf("%s",s);

    int ans=0;

    int x=0;

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



        if(s[i]==s[i+1]){

            x++;

        }else{

            ans+=x;

            x=0;

        }

    }

    ans+=x;

    cout<<min(n-1,ans+k*2)<<endl;

	return 0;

}




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

#include<cstdlib>

#include<cstdio>

#include<cmath>

#define N 200020

using namespace std;

int n,k,cnt;

char ch[N];

int main()

{

	scanf("%d%d%s",&n,&k,ch+1);

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

	{

		int j=i;

		while(ch[j+1]==ch[i])j++;

		cnt++;i=j;

	}

	cnt=max(1,cnt-2*k);

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

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;

const int INF = 1e9;



struct Block {

    bool dir = false; // 0 - L, 1 - R

    int cnt = 0;

};



int main() {

    int n, k;

    cin >> n >> k;

    string s;

    cin >> s;

    

    deque<Block> q;

    

    int cnt = 1;

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

        if (i == n || s[i] != s[i - 1]) {

            q.push_back({s[i - 1] == 'R', cnt});

            cnt = 1;

        } else {

            cnt++;

        }

    }

    

    // for (Block &b : q) {

    //     for (int i = 0; i < b.cnt; ++i)

    //         cout << (b.dir ? 'R' : 'L');

    // }

    // cout << '\n';

    

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

        if (q.size() == 1) {

            q[0].dir = !q[0].dir;

        } else if (q.size() == 2) {

            q[1].cnt += q[0].cnt;

            q.pop_front();

        } else {

            q[2].cnt += q[0].cnt;

            q[2].cnt += q[1].cnt;

            q.pop_front();

            q.pop_front();

        }

    }

    

    int ans = 0;

    for (Block &b : q) {

        ans += b.cnt - 1;

        // for (int i = 0; i < b.cnt; ++i)

        //     cout << (b.dir ? 'R' : 'L');

    }

    // cout << '\n';

        

    cout << ans;

}

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

#include<algorithm>

#include<cmath>

#define ll long long

#define N 100005

#define inf 0x3fffffff

#define rep(i, l, r) for(int i=l; i<=r; ++i)

using namespace std;

int n, k;

char s[N];

int main(){

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

    int tmp=0;

    rep(i, 0, n-1){

        if(!i || s[i]!=s[i-1]) ++tmp;

    }

    tmp=max(1, tmp-2*k);

    printf("%d", n-tmp);

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <algorithm>

#include <string>

using namespace std;

int main() {

	long long n, k;

	string s;

	cin >> n >> k >> s;

	long long p = 0, d = 0;

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

		if (s[i] == s[i + 1]) ++p;

		else ++d;

	if (k >= d / 2) p += d / 2 * 2, p += d % 2 == 1 && k >= d / 2 + 1 ? 1 : 0;

	else p += k * 2;

	cout << p;

	return 0;

}






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

#include<algorithm>

#include<cmath>

#define ll long long

#define N 100005

#define inf 0x3fffffff

#define rep(i, l, r) for(int i=l; i<=r; ++i)

using namespace std;

int n, k;

char s[N];

int main(){

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

    int tmp=0;

    rep(i, 0, n-1){

        if(!i || s[i]!=s[i-1]) ++tmp;

    }

    tmp=max(1, tmp-2*k);

    printf("%d", n-tmp);

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int n, k;

string s;



int main() {

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

    cin >> n >> k;

    cin >> s;

    int ret = 0;

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

        if (s[i] == s[i - 1]) ret++;

    cout << min(ret + 2 * k, n - 1) << endl; 

}

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

#include<algorithm>

#include<cmath>

#define ll long long

#define N 100005

#define inf 0x3fffffff

#define rep(i, l, r) for(int i=l; i<=r; ++i)

using namespace std;

int n, k;

char s[N];

int main(){

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

    int tmp=0;

    rep(i, 0, n-1){

        if(!i || s[i]!=s[i-1]) ++tmp;

    }

    tmp=max(1, tmp-2*k);

    printf("%d", n-tmp);

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<algorithm>/*{{{*/

#include<cctype>

#include<cassert>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<iostream>

#include<map>

#include<queue>

#include<set>

#include<vector>

using namespace std;

typedef long long lld;

typedef long double lf;

typedef unsigned long long uld;

typedef pair<int,int> pii;

#define fi first

#define se second

#define pb push_back

#define mk make_pair

#define FOR(i,a,b) for(int i=(a);i<=(b);++i)

#define ROF(i,a,b) for(int i=(a);i>=(b);--i)

namespace RA{

    int r(int p){return 1ll*rand()*rand()%p;}

    int r(int L,int R){return r(R-L+1)+L;}

}

namespace IO{

    char nc(){ static char bf[100000],*p1=bf,*p2=bf; return p1==p2&&(p2=(p1=bf)+ fread(bf,1,100000,stdin),p1==p2)?EOF:*p1++; }

    int rd(){ int res=0; char c=getchar(); while(!isdigit(c))c=getchar(); while(isdigit(c))res=res*10+c-'0',c=getchar(); return res; }

}/*}}}*/

/******************heading******************/

const int N=1e5+5;



int n,k,ans;

char s[N];

int sig,c[2];



int main(){

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

    scanf("%s",s+1);

    FOR(i,1,n){

        if(s[i]!=s[i-1])sig=!sig,c[sig]++;

        else ans++;

    }

    //printf("%d %d\n",c[0],c[1]);

    if(c[0]>c[1])swap(c[0],c[1]);

    if(k<c[0])ans+=k*2;

    else ans=n-1;

    printf("%d",ans);

    return 0;

}


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

#include<algorithm>

#include<cmath>

#define ll long long

#define N 100005

#define inf 0x3fffffff

#define rep(i, l, r) for(int i=l; i<=r; ++i)

using namespace std;

int n, k;

char s[N];

int main(){

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

    int tmp=0;

    rep(i, 0, n-1){

        if(!i || s[i]!=s[i-1]) ++tmp;

    }

    tmp=max(1, tmp-2*k);

    printf("%d", n-tmp);

    return 0;

}

// Fastest known solution for this problem: