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 vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using ll = long long int;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using cdouble = complex<double>;
const double eps = 1e-9;
const double INFD = numeric_limits<double>::infinity();
bool nearlyeq(double x, double y) { return abs(x - y) < eps; }
bool inrange(ll x, ll t) { return x >= 0 && x < t; }
bool inrange(vll xs, ll t) {
  for (auto x : xs)
    if (!(x >= 0 && x < t)) return false;
  return true;
}
int ceillog2(ll x) {
  int ret = 0;
  x--;
  while (x > 0) {
    ret++;
    x >>= 1;
  }
  return ret;
}
ll rndf(double x) { return (ll)(x + (x >= 0 ? 0.5 : -0.5)); }
ll floorsqrt(ll x) {
  ll m = (ll)sqrt((double)x);
  return m + (m * m <= x ? 0 : -1);
}
ll ceilsqrt(ll x) {
  ll m = (ll)sqrt((double)x);
  return m + (x <= m * m ? 0 : 1);
}
ll rnddiv(ll a, ll b) { return (a / b + (a % b * 2 >= b ? 1 : 0)); }
ll ceildiv(ll a, ll b) { return (a / b + (a % b == 0 ? 0 : 1)); }
ll gcd(ll m, ll n) {
  if (n == 0)
    return m;
  else
    return gcd(n, m % n);
}
ll lcm(ll m, ll n) { return m * n / gcd(m, n); }
class SegTree {
 private:
  struct val_t {
    bool enable;
    ll upd, add, min, max, sum;
  };
  int n, N;
  int base;
  vector<val_t> nodes;
  int left_of(int id) {
    if (id >= base)
      return -1;
    else
      return id * 2 + 1;
  }
  int right_of(int id) {
    if (id >= base)
      return -1;
    else
      return id * 2 + 2;
  }
  int parent_of(int id) {
    if (id == 0)
      return -1;
    else
      return (id - 1) >> 1;
  }
  void merge(int id, int id_l, int id_r) {
    nodes[id].min = min(nodes[id_l].min + nodes[id_l].add,
                        nodes[id_r].min + nodes[id_r].add);
    nodes[id].max = max(nodes[id_l].max + nodes[id_l].add,
                        nodes[id_r].max + nodes[id_r].add);
    nodes[id].sum = nodes[id_l].sum + nodes[id_l].add * cover_size(id_l) +
                    nodes[id_r].sum + nodes[id_r].add * cover_size(id_r);
  }
  void lazy_rec(int s, int t, int l, int r, int id, ll upd, ll add,
                bool enable) {
    if (s == l && t == r) {
      if (enable)
        nodes[id] = {true, upd, add, upd, upd, upd * cover_size(id)};
      else
        nodes[id].add += add;
    } else {
      int m = (l + r) / 2;
      int id_l = left_of(id);
      int id_r = right_of(id);
      if (!enable) {
        add += nodes[id].add;
        if (nodes[id].enable) {
          upd = nodes[id].upd;
          enable = true;
        }
      }
      nodes[id].enable = false;
      nodes[id].add = 0;
      if (s < m && m < t) {
        lazy_rec(s, m, l, m, id_l, upd, add, enable);
        lazy_rec(m, t, m, r, id_r, upd, add, enable);
      } else if (s < m) {
        lazy_rec(s, t, l, m, id_l, upd, add, enable);
        lazy_rec(0, 0, 0, 0, id_r, upd, add, enable);
      } else if (m < t) {
        lazy_rec(0, 0, 0, 0, id_l, upd, add, enable);
        lazy_rec(s, t, m, r, id_r, upd, add, enable);
      }
      merge(id, id_l, id_r);
    }
  }
  enum change_t { UPD, ADD };
  void change_rec(int s, int t, int l, int r, int id, ll x, change_t op) {
    if (s == l && t == r) {
      if (op == UPD)
        nodes[id] = {true, x, 0, x, x, x * cover_size(id)};
      else if (op == ADD)
        nodes[id].add += x;
    } else {
      int m = (l + r) / 2;
      int id_l = left_of(id);
      int id_r = right_of(id);
      if (s < m && m < t) {
        change_rec(s, m, l, m, id_l, x, op);
        change_rec(m, t, m, r, id_r, x, op);
      } else if (s < m) {
        change_rec(s, t, l, m, id_l, x, op);
      } else if (m < t) {
        change_rec(s, t, m, r, id_r, x, op);
      }
      merge(id, id_l, id_r);
    }
  }
  enum solve_t { MIN, MAX, SUM };
  ll solve_rec(int s, int t, int l, int r, int id, solve_t op) {
    ll v = 0;
    if (s == l && t == r) {
      if (op == MIN)
        v = nodes[id].min;
      else if (op == MAX)
        v = nodes[id].max;
      else if (op == SUM)
        v = nodes[id].sum;
    } else {
      int m = (l + r) / 2;
      int id_l = left_of(id);
      int id_r = right_of(id);
      if (s < m && m < t) {
        ll v0 = solve_rec(s, m, l, m, id_l, op);
        ll v1 = solve_rec(m, t, m, r, id_r, op);
        if (op == MIN)
          v = min(v0, v1);
        else if (op == MAX)
          v = max(v0, v1);
        else if (op == SUM)
          v = v0 + v1;
      } else if (s < m) {
        v = solve_rec(s, t, l, m, id_l, op);
      } else if (m < t) {
        v = solve_rec(s, t, m, r, id_r, op);
      }
    }
    if (op == MIN)
      v += nodes[id].add;
    else if (op == MAX)
      v += nodes[id].add;
    else if (op == SUM)
      v += nodes[id].add * (t - s);
    return v;
  }
  void lazy(int s, int t) { lazy_rec(s, t, 0, N, 0, 0, 0, false); }

 public:
  SegTree(int n, ll init) {
    this->n = n;
    N = (int)pow(2, ceil(log2(n)));
    base = N - 1;
    nodes = vector<val_t>(base + N, {false, 0, 0, LLONG_MAX, LLONG_MIN, 0});
    upd(0, n, init);
  }
  int cover_size(int id) {
    int cnt = 1;
    while (left_of(id) != -1) {
      id = left_of(id);
      cnt *= 2;
    }
    int l = id - base;
    int r = min(l + cnt, n);
    return max(0, r - l);
  }
  void upd(int s, int t, ll x) {
    lazy(s, t);
    change_rec(s, t, 0, N, 0, x, UPD);
  }
  void add(int s, int t, ll x) {
    lazy(s, t);
    change_rec(s, t, 0, N, 0, x, ADD);
  }
  ll minof(int s, int t) {
    lazy(s, t);
    return solve_rec(s, t, 0, N, 0, MIN);
  }
  ll maxof(int s, int t) {
    lazy(s, t);
    return solve_rec(s, t, 0, N, 0, MAX);
  }
  ll sumof(int s, int t) {
    lazy(s, t);
    return solve_rec(s, t, 0, N, 0, SUM);
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ;
  int n;
  cin >> n;
  ll x;
  cin >> x;
  vll a(n);
  for (int i = 0; i < int(n); i++) cin >> a[i];
  SegTree *st = new SegTree(n, LLONG_MAX);
  for (int i = 0; i < int(n); i++) {
    st->upd(i, i + 1, a[i]);
  }
  ll ans = LLONG_MAX;
  for (int i = 0; i < int(n); i++) {
    ll buf = x * i;
    for (int j = 0; j < int(n); j++) {
      int id = j - i;
      ll b;
      if (id >= 0) {
        b = st->minof(j - i, j + 1);
      } else {
        b = min(st->minof(0, j + 1), st->minof(n + j - i, n));
      }
      buf += b;
    }
    ans = min(ans, buf);
  }
  cout << ans << endl;
}
