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;
const long long INF = LLONG_MAX - 100;
const long long mod = 2e9 + 7;
const long long MAX_N = 5e5 + 5;
long long dx[] = {-(long long)1, 0, (long long)1, 0},
          dy[] = {0, (long long)1, 0, -(long long)1};
vector<long long> prime;
long long inv[MAX_N], fac[MAX_N];
template <class T = long long>
T in() {
  T x;
  cin >> x;
  return (x);
}
inline long long GCD(long long a, long long b) {
  long long c;
  while (b != 0) {
    c = a % b;
    a = b;
    b = c;
  }
  return a;
}
inline long long LCM(long long a, long long b) { return a * b / GCD(a, b); }
inline long long POW(long long a, long long b) {
  long long c = (long long)1;
  while (b > 0) {
    if (b & (long long)1) {
      c = a * c % mod;
    }
    a = a * a % mod;
    b >>= (long long)1;
  }
  return c;
}
inline void _nCr() {
  fac[0] = (long long)1;
  for (long long i = (long long)1; i < MAX_N; i++) {
    fac[i] = fac[i - (long long)1] * i % mod;
  }
  for (long long i = 0; i < MAX_N; i++) {
    inv[i] = POW(fac[i], mod - 2);
  }
}
inline long long nCr(long long n, long long r) {
  return (fac[n] * inv[r] % mod) * inv[n - r] % mod;
}
inline void PRI(long long n) {
  bool a[n + (long long)1];
  for (long long i = 0; i < n + (long long)1; i++) {
    a[i] = (long long)1;
  }
  for (long long i = 2; i < n + (long long)1; i++) {
    if (a[i]) {
      prime.push_back(i);
      long long b = i;
      while (b <= n) {
        a[b] = 0;
        b += i;
      }
    }
  }
}
class UnionFind {
 private:
  vector<long long> par;

 public:
  UnionFind(long long N) { par = vector<long long>(N, -(long long)1); }
  long long find(long long x);
  long long size(long long x);
  void unite(long long x, long long y);
  bool same(long long x, long long y);
};
class Kruskal {
 private:
  UnionFind *uf;
  vector<pair<long long, pair<long long, long long>>> e;

 public:
  vector<pair<long long, pair<long long, long long>>> mst;
  Kruskal(long long N) { uf = new UnionFind(N); }
  void add(long long x, long long y, long long z);
  void run();
};
long long UnionFind::find(long long x) {
  if (par[x] < 0)
    return x;
  else
    return par[x] = find(par[x]);
}
long long UnionFind::size(long long x) { return -par[find(x)]; }
void UnionFind::unite(long long x, long long y) {
  x = find(x);
  y = find(y);
  if (size(x) < size(y)) swap(x, y);
  par[x] += par[y];
  par[y] = x;
}
bool UnionFind::same(long long x, long long y) {
  x = find(x);
  y = find(y);
  return x == y;
}
void Kruskal::add(long long x, long long y, long long z) {
  if (x > y) swap(x, y);
  e.push_back({z, {x, y}});
}
void Kruskal::run() {
  sort(e.begin(), e.end());
  e.erase(unique(e.begin(), e.end()), e.end());
  for (auto x : e) {
    if (uf->same(x.second.first, x.second.second)) {
      continue;
    } else {
      mst.push_back(x);
      uf->unite(x.second.first, x.second.second);
    }
  }
}
signed main() {
  long long n, x;
  cin >> n >> x;
  long long a[n];
  long long mi[n];
  long long cnt[n];
  for (long long(i) = (0); (i) < (n); (i)++) {
    cin >> a[i];
    mi[i] = INF;
    cnt[i] = INF;
  }
  for (long long(i) = (0); (i) < (n); (i)++) {
    for (long long(j) = (0); (j) < (n); (j)++) {
      if (mi[(i + j) % n] > a[i] + x * j) {
        mi[(i + j) % n] = a[i] + x * j;
        cnt[(i + j) % n] = j;
      }
    }
  }
  long long ans = 0;
  long long cntsum = 0;
  long long ma = 0;
  for (long long(i) = (0); (i) < (n); (i)++) {
    ans += mi[i];
    cntsum += cnt[i];
    ma = max(ma, cnt[i]);
  }
  ans -= (cntsum - ma) * x;
  cout << ans << endl;
}
