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>
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;
struct edge {
  int from, to;
  ll cost;
};
class Eratosthenes {
 public:
  vector<bool> prime;
  Eratosthenes(int size) {
    prime.resize(size + 1, 1);
    prime[0] = 0;
    prime[1] = 0;
    for (ll i = 2; i <= (ll)size; ++i) {
      if (prime[i]) {
        for (int j = 2 * i; j <= size; j += i) {
          prime[j] = 0;
        }
      }
    }
  }
};
class Combination {
  vector<ll> fac;
  vector<ll> ifac;

 public:
  Combination(ll size) {
    fac.resize(size);
    ifac.resize(size);
    fac[0] = 1;
    ifac[0] = 1;
    for (ll i = 0; i < size; i++) {
      fac[i + 1] = fac[i] * (i + 1) % MOD;
      ifac[i + 1] = ifac[i] * mpow(i + 1, MOD - 2) % MOD;
    }
  }
  ll mpow(ll x, ll n) {
    ll ans = 1;
    while (n != 0) {
      if (n & 1) ans = ans * x % MOD;
      x = x * x % MOD;
      n = n >> 1;
    }
    return ans;
  }
  ll comb(ll a, ll b) {
    if (a == 0 && b == 0) return 1;
    if (a < b || a < 0) return 0;
    ll tmp = ifac[a - b] * ifac[b] % MOD;
    return tmp * fac[a] % MOD;
  }
};
ll GCD(ll a, ll b) {
  if (b == 0) return a;
  return GCD(b, a % b);
}
ll N, x;
bool v[101010];
int main() {
  cin >> N >> x;
  vector<ll> A(N), C(N, 2e9);
  ll mm = 0, m = 1, c = 0;
  for (int i = 0; i < N; ++i) cin >> A[i];
  for (int i = 0; i < N; ++i) {
    for (int k = 0; k < N; ++k) {
      if (v[k]) continue;
      int p = (k + m >= N ? (k + m) % (N) : k + m);
      if (A[k] + x * m <= A[p]) {
        v[p] = true;
        mm = max(mm, m);
        C[p] = min(C[p], A[k]);
      }
    }
    m++;
  }
  for (int i = 0; i < N; ++i) {
    if (!v[i])
      c += A[i];
    else
      c += C[i];
  }
  cout << c + x * mm << endl;
  return 0;
}
