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

#include<map>

#include<set>

#include<queue>

#include<algorithm>

#define MAXN 100006

using namespace std;

int n,fa[MAXN],u,v,top,p[MAXN];

map<int,int> h[MAXN];

set<int> e[MAXN];

queue<pair<int,int> > q;

void link(int u,int v)

{

	e[u].insert(v);

	e[v].insert(u);

	if(u>v) swap(u,v);

	++h[u][v];

	if(h[u][v]==2) q.push(make_pair(u,v));

	if(h[u][v]>2)

	{

		printf("NO");

		exit(0);

	}

}

void cut(int u,int v)

{

	e[u].erase(v);

	if(u>v) swap(u,v);

	h[u].erase(v);

}

int find(int x)

{

	if(x!=fa[x]) fa[x]=find(fa[x]);

	return fa[x];

}

int main()

{

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

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

	scanf("%d",&n);

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

		fa[i]=i;

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

	{

		scanf("%d%d",&u,&v);

		link(u,v);

	}

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

	{

		scanf("%d%d",&u,&v);

		link(u,v);

	}

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

	{

		do

		{

			if(q.empty())

			{

				printf("NO");

				return 0;

			}

			u=q.front().first;

			v=q.front().second;

			u=find(u);

			v=find(v);

			q.pop();

		}while(u==v);

		if(e[u].size()>e[v].size()) swap(u,v);

		fa[u]=v;

		cut(v,u);

		top=0;		

		for(set<int>::iterator it=e[u].begin();it!=e[u].end();it++)

			p[++top]=*it;

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

		{

			int x=p[i];

			x=find(x);

			if(x==v) continue;

			link(x,v);

			cut(x,u);

		}

		e[u].clear();

	}

	printf("YES");

}

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

using namespace std;

typedef long long ll;

#define rg register



template <typename _Tp> inline _Tp read(_Tp&x){

	char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();

	while(isdigit(c11))x=x*10+c11-'0',c11=getchar();return x;

}



const int N=101000,ae=20;

struct Edge{int v,nxt;}a[N*ae*2];

int qx[N*ae],qy[N*ae],dad[N];

int head[N],_,sz[N];

int n,he=1,ta=0;



inline int find(int x){return dad[x]?dad[x]=find(dad[x]):x;}



inline void ins(int u,int v){++sz[u],a[++_].v=v,a[_].nxt=head[u],head[u]=_;}



map <ll,int> cnt;



#define h(x,y) (x+1ll*n*y)

inline void add(int x,int y){

	if(x>y)swap(x,y);

	ins(x,y),ins(y,x);

	if((++cnt[h(x,y)])==2)

		++ta,qx[ta]=x,qy[ta]=y;

}



int main(){

	read(n);int x,y,p;

	for(rg int i=n-2+n;i;--i)read(x),read(y),add(x,y);

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

		do	x=qx[he],y=qy[he],++he;

		while(find(x)==find(y)&&he<=ta);

		x=find(x),y=find(y);

		if(x==y){puts("NO");return 0;}

		if(sz[x]>sz[y])swap(x,y);

		--sz[y];cnt.erase(x<y?h(x,y):h(y,x));

		for(rg int j=head[x];j;j=a[j].nxt){

			p=find(a[j].v);

			if(p^y)if(p!=find(x))add(p,y);

		}

		dad[x]=y;

	}puts("YES");

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

using namespace std;

#define pii pair<int,int>

#define mk make_pair

pii q[200001];

int h,t;

int n;

set<int> s[200001];

map<pii,int> mp;

int fa[200001];

int findfa(int x){

	return x==fa[x]?fa[x]:fa[x]=findfa(fa[x]);

}

int main(){

	scanf("%d",&n);

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

		int u,v;

		scanf("%d%d",&u,&v);

		mp[mk(u,v)]++;mp[mk(v,u)]++;

		s[u].insert(v),s[v].insert(u);

		if(mp[mk(u,v)]==2)q[++t]=mk(u,v);

	}

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

	set<int>::iterator id;

	while(h<t){

		int u=q[++h].first,v=q[h].second;

		u=findfa(u),v=findfa(v);

		s[u].erase(v),s[v].erase(u);

		if(s[u].size()<s[v].size())swap(u,v);

		for(id=s[v].begin();id!=s[v].end();++id){

			int to=(*id);

			mp[mk(v,to)]=mp[mk(to,v)]=0;

			s[to].erase(v);s[to].insert(u);

			mp[mk(u,to)]++,mp[mk(to,u)]++;

			if(mp[mk(u,to)]==2){

				q[++t]=mk(u,to);

			}

			s[u].insert(to);

		}

		fa[v]=u;

		s[v].clear();

	}

	int ans=0;

	for(int i=1;i<=n;++i)ans+=fa[i]==i;

	if(ans==1)puts("YES");

	else puts("NO");

}

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

using namespace std;

namespace IO {

  const int IN_LEN = 1 << 18 | 1;

  static char buf[IN_LEN] , *s , *t;

  inline int Getchar( void ) { return s == t && ( t = ( s = buf ) + fread( buf , 1 , IN_LEN , stdin ) ) , s == t ? -1 : *s++; }

  template <class T> inline void read( T & x ) {

    static int c , f;

    for( c = Getchar() , f = 0 ; c < '0' || c > '9' ; c = Getchar() ) if( c == '-' ) f = 1;

    for( x = 0 ; c <= '9' && c >= '0' ; c = Getchar() ) x = x * 10 + c - 48;

    x = f ? -x : x;

  }

}using IO::read;

const int MAXN = 1e5 + 1;

typedef pair<int,int> pii;

set<int> E[MAXN];

map<pii,int> rem;

int n , f[MAXN];

queue<pii> Q;

pii get( int x , int y ) { if( x > y ) swap( x , y ); return make_pair( x , y ); }

int find( const int & x ) { return x == f[x] ? x : f[x] = find( f[x] ); }

int main( void ) {

  read( n );

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

    read( u ) , read( v );

    ++rem[get( u , v )];

    E[u].insert( v ) , E[v].insert( u );

  }

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

    read( u ) , read( v );

    ++rem[get( u , v )];

    E[u].insert( v ) , E[v].insert( u );

    if( rem[get( u , v )] == 2 ) Q.push( pii( u , v ) );

  }

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

  while( !Q.empty() ) {

    int u = Q.front().first , v = Q.front().second;Q.pop();

    if( ( u = find( u ) ) == ( v = find( v ) ) ) continue;

    if( E[u].size() < E[v].size() ) swap( u , v );

    for( int k : E[v] ) {

      rem[get( u , v )] = 0;

      E[u].insert( k ) , E[k].insert( u );

      ++rem[get( u , k )];

      if( rem[get( u , k )] == 2 ) Q.push( pii( u , k ) );

    }

    f[v] = u;

    E[v].clear();

  }

  int cnt = 0;

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

    find( i );

    cnt += ( i == f[i] );

  }

  puts( cnt == 1 ? "YES" : "NO" );

  return 0;

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

#include<cstring>

#include<set>

#include<queue>

#include<algorithm>

using namespace std;

const int N=100005;

typedef pair<int,int> pi;

typedef set<int>::iterator sit;

int n,fa[N],cnt;

queue<pi> q;

set<int> G1[N],G2[N];

int find_father(int x){

	if(fa[x]==x)

        return x;

	return fa[x]=find_father(fa[x]);

}

int main()

{

	scanf("%d",&n);

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

        fa[i]=i;

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

		int u,v;

		scanf("%d%d",&u,&v);

		G1[u].insert(v);

		G1[v].insert(u);

	}

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

		int u,v;

		scanf("%d%d",&u,&v);

		G2[u].insert(v);

		G2[v].insert(u);

		if(G1[u].find(v)!=G1[u].end())

            q.push(pi(u,v));

	}

	while(!q.empty()){

		int u=q.front().first,v=q.front().second;

		q.pop();

		u=find_father(u),v=find_father(v);

		if(u==v)

            continue;

		if(G1[u].size()+G2[u].size()>G1[v].size()+G2[v].size())

            swap(u,v);

		fa[u]=v;

		G1[u].erase(v);

		G1[v].erase(u);

		G2[u].erase(v);

		G2[v].erase(u);

		for(sit it=G1[u].begin();it!=G1[u].end();it++){

			int x=*it;

			G1[x].erase(u);

			G1[x].insert(v);

			G1[v].insert(x);

			if(G2[x].find(v)!=G2[x].end())

                q.push(pi(x,v));

		}

		for(sit it=G2[u].begin();it!=G2[u].end();it++){

			int x=*it;

			G2[x].erase(u);

			G2[x].insert(v);

			G2[v].insert(x);

			if(G1[x].find(v)!=G1[x].end())

                q.push(pi(x,v));

		}

	}

	int cnt=0;

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

		if(find_father(i)==i)

            cnt++;

	puts(cnt==1?"YES":"NO");

}


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

#include<cstdio>

#include<map>

#include<set>

#include<queue>

using namespace std;

const int N=100001;

int n;

map<pair<int,int>,int> book;

set<int> e[N];

queue<pair<int,int> >q;

int f[N];

int find(int v)

{

	if(v==f[v]) return v;

	f[v]=find(f[v]);

	return f[v];

}

pair<int,int> make(int x,int y)

{

    if(x>y) swap(x,y);

    return make_pair(x,y);

}

int main()

{

    scanf("%d",&n);

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

    	f[i]=i;

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

	{

        int x,y;

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

        e[x].insert(y);

		e[y].insert(x);

        pair<int,int> t=make(x,y);

        book[t]++;

        if(book[t]==2) q.push(t);

        if(book[t]>2)

        {

        	printf("NO");

        	return 0;

		}

    }

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

	{

        if(q.empty())

        {

        	printf("NO");

        	return 0;

		}

        int x=0,y=0;

        while(x==y)

        {

        	x=find(q.front().first),y=find(q.front().second);

        	q.pop();

		}

        if(e[x].size()>e[y].size()) swap(x,y);

        f[x]=y;

        for(set<int>::iterator it=e[x].begin();it!=e[x].end();it++)

		{

            int v=find(*it);

            e[v].erase(e[v].find(x));

            if(v==y) continue;

            e[v].insert(y),e[y].insert(v);

            pair<int,int> t=make(v,y);

            book[t]++;

            if(book[t]==2) q.push(t);

        }

        e[x].clear();

    }

    printf("YES");

    return 0;

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

using namespace std;

#define N 100005

set<int>s[N];

map<int,int>mat[N];

queue<pair<int,int> >q;

int n,x,y,ans,f[N];

int find(int k){

	if (k==f[k])return k;

	return f[k]=find(f[k]);

}

void add(int x,int y){

	s[x].insert(y);

	s[y].insert(x);

	if (x>y)swap(x,y);

	if (++mat[x][y]==2){

		q.push(make_pair(x,y));

		mat[x][y]=0;

	}

}

void merge(int x,int y){

	if (s[x].size()>s[y].size())swap(x,y);

	f[x]=y;

	for(set<int>::iterator it=s[x].begin();it!=s[x].end();it++){

		int z=find(*it);

		if (y==z)continue;

		add(y,z);

		s[z].erase(x);

	}

	s[x].clear();

}

int main(){

	scanf("%d",&n);

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

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

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

		add(x,y);

	}

	while (!q.empty()){

		ans++;

		merge(find(q.front().first),find(q.front().second));

		q.pop();

	}

	if (ans==n-1)printf("YES");

	else printf("NO");

}

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

#include<cstdio>

#include<map>

#include<set>

#include<queue>

using namespace std;

const int N=100001;

int n;

map<pair<int,int>,int> book;

set<int> e[N];

queue<pair<int,int> >q;

int f[N];

int find(int v)

{

	if(v==f[v]) return v;

	f[v]=find(f[v]);

	return f[v];

}

pair<int,int> make(int x,int y)

{

    if(x>y) swap(x,y);

    return make_pair(x,y);

}

int main()

{

    scanf("%d",&n);

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

    	f[i]=i;

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

	{

        int x,y;

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

        e[x].insert(y);

		e[y].insert(x);

        pair<int,int> t=make(x,y);

        book[t]++;

        if(book[t]==2) q.push(t);

        if(book[t]>2)

        {

        	printf("NO");

        	return 0;

		}

    }

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

	{

        if(q.empty())

        {

        	printf("NO");

        	return 0;

		}

        int x=0,y=0;

        while(x==y)

        {

        	x=find(q.front().first),y=find(q.front().second);

        	q.pop();

		}

        if(e[x].size()>e[y].size()) swap(x,y);

        f[x]=y;

        for(set<int>::iterator it=e[x].begin();it!=e[x].end();it++)

		{

            int v=find(*it);

            e[v].erase(e[v].find(x));

            if(v==y) continue;

            e[v].insert(y),e[y].insert(v);

            pair<int,int> t=make(v,y);

            book[t]++;

            if(book[t]==2) q.push(t);

        }

        e[x].clear();

    }

    printf("YES");

    return 0;

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

using namespace std;

int n;

int a[100005];

int x[100005];

int y[100005];



int main(){

  scanf("%d",&n);

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

    cin>>a[i];

  }



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

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

  

  int ans=0;

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

    int p=i,c=0;

    while(x[p]==-1){

      x[p]=c++;

      y[p]=i;

      p=(p+a[p])%n;

    }

    if(y[p]==i)ans+=(c-x[p]);

  }



  cout<<ans<<endl;

  return 0;

}

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

int n,i,p,c,ans=0;

int a[100000];

int x[100000];

int y[100000];



int main(){

  scanf("%d",&n);

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

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

    x[i]=-1;

    y[i]=-1;

  }

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

    p=i;

    c=0;

    while(x[p]==-1){

      x[p]=c++;

      y[p]=i;

      p=(p+a[p])%n;

    }

    if(y[p]==i)ans+=(c-x[p]);

  }

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

  return 0;

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

#include <iostream>

#include <sstream>

#include <iomanip>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cctype>

#include <cstring>

#include <vector>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <iterator>

#include <bitset>

#include <ctime>

#include<unordered_set>

#include<complex>

using namespace std;



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

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

#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)

#define FILL(a,value) memset(a, value, sizeof(a))



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

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

#define PB push_back

#define MP make_pair



typedef long long LL;

typedef vector<int> VI;

typedef pair<int, int> PII;



const double PI = acos(-1.0);

const int INF = 1000 * 1000 * 1000 + 7;

const LL LINF = INF * (LL)INF;



const int MAX = 2000 + 47;



int A[MAX];

int B[MAX];

int B1[MAX];



int main()

{

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

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

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

	int n; 

	LL x;

	cin >> n >> x;

	FOR(i, 0, n)

	{

		cin >> A[i];

		B[i] = A[i];

	}



	LL ans = LINF;

	FOR(k, 0, n)

	{

		LL summ = 0;

		FOR(i, 0, n) summ += B[i];

		ans = min(ans, k * x + summ);

		FOR(i, 0, n)

		{

			B1[i] = min(A[i], B[(i - 1 + n) % n]);

		}



		FOR(i, 0, n)

		{

			B[i] = B1[i];

		}

	}



	cout << ans << endl;

}


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

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN=2005;



int N,x;

int A[MAXN];

int best[MAXN][MAXN];



int main()

{

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

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

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

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

    {

        best[i][0]=A[i];

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

            best[i][k]=min(best[i][k-1],A[(i-k+N-1)%N+1]);

    }

    long long ans=0x3F3F3F3F3F3F3F3FLL;

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

    {

        long long tmp=0;

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

            tmp+=best[i][k];

        ans=min(ans,tmp+1LL*k*x);

    }

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



    fclose(stdin);

    fclose(stdout);

    return 0;

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



using namespace std;



long long n, x;

long long colors[2010], shift[2010];



int main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(0);



    cin >> n >> x;



    int inicial;

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

        cin >> colors[i];

        shift[0] += colors[i];

    }



    long long best, aux;

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

        best = colors[c];

        for(int i = (c - 1 + n) % n, j = 1; i != c; --i, i+= n, i %= n, ++j){

            if(colors[i] < best)

                best = colors[i];

            shift[j] += best;

        }

    }



    long long corrimientos = 0, menor = shift[0];

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

        if(shift[i] + x * i < menor){

            corrimientos = i;

            menor = shift[i] + x * i;

        }

    }



    cout << menor << endl;



    return 0;

}


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

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN=2005;



int N,x;

int A[MAXN];

int best[MAXN][MAXN];



int main()

{

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

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

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

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

    {

        best[i][0]=A[i];

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

            best[i][k]=min(best[i][k-1],A[(i-k+N-1)%N+1]);

    }

    long long ans=0x3F3F3F3F3F3F3F3FLL;

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

    {

        long long tmp=0;

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

            tmp+=best[i][k];

        ans=min(ans,tmp+1LL*k*x);

    }

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



    fclose(stdin);

    fclose(stdout);

    return 0;

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

#include <iostream>

#include <sstream>

#include <iomanip>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cctype>

#include <cstring>

#include <vector>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <iterator>

#include <bitset>

#include <ctime>

#include<unordered_set>

#include<complex>

using namespace std;



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

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

#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)

#define FILL(a,value) memset(a, value, sizeof(a))



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

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

#define PB push_back

#define MP make_pair



typedef long long LL;

typedef vector<int> VI;

typedef pair<int, int> PII;



const double PI = acos(-1.0);

const int INF = 1000 * 1000 * 1000 + 7;

const LL LINF = INF * (LL)INF;



const int MAX = 2000 + 47;



int A[MAX];

int B[MAX];

int B1[MAX];



int main()

{

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

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

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

	int n; 

	LL x;

	cin >> n >> x;

	FOR(i, 0, n)

	{

		cin >> A[i];

		B[i] = A[i];

	}



	LL ans = LINF;

	FOR(k, 0, n)

	{

		LL summ = 0;

		FOR(i, 0, n) summ += B[i];

		ans = min(ans, k * x + summ);

		FOR(i, 0, n)

		{

			B1[i] = min(A[i], B[(i - 1 + n) % n]);

		}



		FOR(i, 0, n)

		{

			B[i] = B1[i];

		}

	}



	cout << ans << endl;

}


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

#include<cstring>

using namespace std;

typedef long long LL;

#define MAXN 2000

LL a[MAXN+5];

LL b[MAXN+5][MAXN+5];

LL abs(LL x)

{

	return x>=0 ? x:-x; 

}

LL min(LL x,LL y)

{

	return x<y ? x : y;

}

LL read()

{

	LL x=0,f=1;

	char c=getchar();

	while('0'>c||c>'9'){if(c=='-') f=-1;c=getchar();}

	while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();}

	return x*f;

}

int main()

{

	int n;

    LL x,sum = 1LL << 60LL;

    n=read(),x=read();

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

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

        b[i][0] = a[i];

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

            int pos = i - k;

            if(pos <= 0) pos = n - abs(pos);

            b[i][k] = min(b[i][k - 1],a[pos]);

        }

    }

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

        LL ans = 0;

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

            ans += b[i][k];

        }

        sum = min(sum,ans + x * k);

    }

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

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



using namespace std;



long long n, x;

long long colors[2010], shift[2010];



int main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(0);



    cin >> n >> x;



    int inicial;

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

        cin >> colors[i];

        shift[0] += colors[i];

    }



    long long best, aux;

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

        best = colors[c];

        for(int i = (c - 1 + n) % n, j = 1; i != c; --i, i+= n, i %= n, ++j){

            if(colors[i] < best)

                best = colors[i];

            shift[j] += best;

        }

    }



    long long corrimientos = 0, menor = shift[0];

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

        if(shift[i] + x * i < menor){

            corrimientos = i;

            menor = shift[i] + x * i;

        }

    }



    cout << menor << endl;



    return 0;

}


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

#include<cstring>

using namespace std;

typedef long long LL;

#define MAXN 2000

LL a[MAXN+5];

LL b[MAXN+5][MAXN+5];

LL abs(LL x)

{

	return x>=0 ? x:-x; 

}

LL min(LL x,LL y)

{

	return x<y ? x : y;

}

LL read()

{

	LL x=0,f=1;

	char c=getchar();

	while('0'>c||c>'9'){if(c=='-') f=-1;c=getchar();}

	while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();}

	return x*f;

}

int main()

{

	int n;

    LL x,sum = 1LL << 60LL;

    n=read(),x=read();

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

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

        b[i][0] = a[i];

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

            int pos = i - k;

            if(pos <= 0) pos = n - abs(pos);

            b[i][k] = min(b[i][k - 1],a[pos]);

        }

    }

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

        LL ans = 0;

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

            ans += b[i][k];

        }

        sum = min(sum,ans + x * k);

    }

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

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

#include <iostream>

#include <sstream>

#include <iomanip>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cctype>

#include <cstring>

#include <vector>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <iterator>

#include <bitset>

#include <ctime>

#include<unordered_set>

#include<complex>

using namespace std;



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

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

#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)

#define FILL(a,value) memset(a, value, sizeof(a))



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

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

#define PB push_back

#define MP make_pair



typedef long long LL;

typedef vector<int> VI;

typedef pair<int, int> PII;



const double PI = acos(-1.0);

const int INF = 1000 * 1000 * 1000 + 7;

const LL LINF = INF * (LL)INF;



const int MAX = 2000 + 47;



int A[MAX];

int B[MAX];

int B1[MAX];



int main()

{

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

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

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

	int n; 

	LL x;

	cin >> n >> x;

	FOR(i, 0, n)

	{

		cin >> A[i];

		B[i] = A[i];

	}



	LL ans = LINF;

	FOR(k, 0, n)

	{

		LL summ = 0;

		FOR(i, 0, n) summ += B[i];

		ans = min(ans, k * x + summ);

		FOR(i, 0, n)

		{

			B1[i] = min(A[i], B[(i - 1 + n) % n]);

		}



		FOR(i, 0, n)

		{

			B[i] = B1[i];

		}

	}



	cout << ans << endl;

}


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

#include<algorithm>

using namespace std;



#define MAXN 2000

int N,X;

int Cost[MAXN+5],Change[MAXN+5][MAXN+5];



int main(){

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

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

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

    long long Ans=1ll<<60,tot=0;

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

        tot+=Change[i][0]=Cost[i];

    Ans=min(Ans,tot);

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

        tot=0;

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

            tot+=Change[i][k]=min(Change[i][k-1],Cost[i-k<1?N+i-k:i-k]);

        Ans=min(Ans,1ll*k*X+tot);

    }

    printf("%lld",Ans);

}