Snuke lives in another world, where slimes are real creatures and kept by some people. Slimes come in N colors. Those colors are conveniently numbered 1 through N. Snuke currently has no slime. His objective is to have slimes of all the colors together.

Snuke can perform the following two actions:

* Select a color i (1≤i≤N), such that he does not currently have a slime in color i, and catch a slime in color i. This action takes him a_i seconds.

* Cast a spell, which changes the color of all the slimes that he currently has. The color of a slime in color i (1≤i≤N-1) will become color i+1, and the color of a slime in color N will become color 1. This action takes him x seconds.




Find the minimum time that Snuke needs to have slimes in all N colors.

Constraints

* 2≤N≤2,000
* a_i are integers.
* 1≤a_i≤10^9
* x is an integer.
* 1≤x≤10^9

Input

The input is given from Standard Input in the following format:


N x
a_1 a_2 ... a_N


Output

Find the minimum time that Snuke needs to have slimes in all N colors.

Examples

Input

2 10
1 100


Output

12


Input

3 10
100 1 100


Output

23


Input

4 10
1 2 3 4


Output

10
#include<bits/stdc++.h>

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

using namespace std;

#define MAX_N 2016

typedef long long ll;

const bool debug = false;

int N,x;
ll a[MAX_N];
ll mini[MAX_N];
bool fin[MAX_N];

//bool check(ll cnt) {
ll compute(ll cnt) {
  if( debug ) {
    puts("");
    cout << "cnt == " << cnt << endl;
  }
  memset(fin,false,sizeof fin);
  rep(i,N) mini[i] = a[i];
  rep(i,N) rep(j,N) if( i != j ) {
    if( i < j ) {
      if( j-i <= cnt ) {
	//mini[j] = min(mini[j],a[i]+(ll)(j-i)*(ll)x);
	mini[j] = min(mini[j],a[i]);
      } else {
      }
    } else { // i > j
      if( (j-i+N) <= cnt ) {
	//mini[j] = min(mini[j],a[i] + (ll)x * (ll)(j-i+N) );
	mini[j] = min(mini[j],a[i]);
      } else {
      }
    }
  }
  ll answer = x * cnt;
  deque<int> sp;
  rep(i,N) {
    if( mini[i] == a[i] ) {
      fin[i] = true;
      answer += a[i];
      sp.push_back(i);
    }
  }
  if( debug ) {
    rep(i,N) {
      cout << "mini[" << i << "] = " << mini[i] << endl;
    }
    cout << "current answer = " << answer << endl;
  }

  rep(i,(int)sp.size()) {
    ll step = 0;
    int cur = (sp[i]+1)%N;
    while( !fin[cur] ) {
      ( cur += 1 ) %= N;
      ++step;
      if( step > cnt ) {
	answer += a[cur];
      } else {
	answer += a[sp[i]];
      }
    }
  }
  return answer;
}

ll ternarySearch(){
  int L = 1, R = N;
  int pL = L, pR = R;
  rep(_,120){
    if( compute(((L+R*2)/3)) < compute(((L*2+R)/3)) ) {
      R = ( L + R * 2 ) / 3;
    } else {
      L = ( L * 2 + R ) / 3;
    }
    if( R == pR && L == pL ) break;
    pR = R, pL = L;
  }
  return compute((int)(((L+R)*0.5)));
}


int main() {
  /*
  cout << 2000 << " " << 1000000000LL << endl;
  rep(i,2000) {
    if( i ) printf(" ");
    cout << 1000000000;
  } puts("");
  return 0;
  */
  cin >> N >> x;
  rep(i,N) cin >> a[i];

  /*
  ans = LLONG_MAX;
  ll L = 0, R = (ll)(N+1);
  while( L + 1 < R ){
    ll M = ( L + R ) / 2;
    if( check(M) ) R = M;
    else           L = M;
  }
  cout << ans << endl;
  */
  ll mini = LLONG_MAX;
  rep(i,sqrt(N+1)) {
    mini = min(compute(i),mini);
  }
  cout << mini << endl;
  /.cout<< ternarySearch() << endl;
  return 0;
}
