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;
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << '\n'; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
struct Convexhull {
  struct Line {
    long long a, b;
    Line(long long a = 0, long long b = 0) : a(a), b(b) {}
    bool operator<(const Line& oth) const {
      return make_pair(-a, b) < make_pair(-oth.a, oth.b);
    }
    bool operator==(const Line& oth) const {
      return make_pair(a, b) == make_pair(oth.a, oth.b);
    }
    bool operator!=(const Line& oth) const {
      return make_pair(a, b) != make_pair(oth.a, oth.b);
    }
  };
  long double intersect(Line ln1, Line ln2) {
    return (double)(ln2.b - ln1.b) / (ln1.a - ln2.a);
  }
  int bad(Line ln1, Line ln2, Line ln3) {
    return (double)(ln1.a - ln2.a) * (ln2.b - ln3.b) >=
           (double)(ln2.a - ln3.a) * (ln1.b - ln2.b);
  }
  set<Line> hull;
  set<pair<double, Line> > pos;
  void clear() {
    hull.clear();
    pos.clear();
  }
  void add(long long a, long long b) {
    Line ln(a, b);
    if (hull.find(ln) != hull.end()) return;
    hull.insert(ln);
    set<Line>::iterator it = hull.find(ln);
    if (it == hull.begin()) {
      pos.insert(make_pair(-1e18, ln));
      if (++it != hull.end()) pos.erase(make_pair(-1e18, *it));
      it--;
    } else {
      Line prv = *(--it);
      it++;
      if (prv.a == ln.a) {
        hull.erase(ln);
        return;
      }
      if (*it != *hull.rbegin()) {
        Line nxt = *(++it);
        it--;
        if (bad(prv, ln, nxt)) {
          hull.erase(ln);
          return;
        }
        pos.erase(make_pair(intersect(prv, nxt), nxt));
      }
    }
    Line u, v;
    if (it != hull.begin()) {
      v = *(--it);
      while (it != hull.begin()) {
        u = *(--it);
        if (bad(u, v, ln)) {
          pos.erase(make_pair(intersect(u, v), v));
          hull.erase(v);
          it = hull.find(v = u);
        } else {
          it++;
          break;
        }
      }
      pos.insert(make_pair(intersect(v, ln), ln));
      it++;
    }
    if (*it != *hull.rbegin()) {
      u = *(++it);
      while (*it != *hull.rbegin()) {
        v = *(++it);
        if (ln.a == u.a || bad(ln, u, v)) {
          pos.erase(make_pair(intersect(u, v), v));
          hull.erase(u);
          it = hull.find(u = v);
        } else {
          it--;
          break;
        }
      }
      pos.insert(make_pair(intersect(ln, u), u));
      it--;
    }
  }
  long long query(long long x) {
    if (!pos.size()) return 1e18;
    set<pair<double, Line> >::iterator it =
        pos.upper_bound(make_pair(x, Line(-1e18, -1e18)));
    it--;
    return it->second.a * x + it->second.b;
  }
};
long long solve(vector<long long> A, long long x) {
  int N = A.size();
  vector<long long> DP(N);
  DP[0] = A[0];
  Convexhull CH;
  CH.add(A[0] + x, A[0]);
  for (int i = 0; i < N; i++) {
    DP[i] = CH.query(i);
    if (i < N - 1) {
      CH.add(A[i + 1] + x, DP[i] - i * A[i + 1] - x * i - x);
    }
  }
  return DP[N - 1];
}
void rotate(vector<long long>& A) {
  vector<long long> B(A.size());
  for (int i = 0; i < A.size(); i++) {
    B[i] = A[(i + 1) % A.size()];
  }
  A = B;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int N, x;
  N = 2000;
  x = 1 << 25;
  cin >> N >> x;
  vector<long long> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  long long ans = 1e18;
  for (int i = 0; i < max(1, N - 1); i++) {
    ans = min(ans, solve(A, x));
    rotate(A);
  }
  cout << ans << '\n';
  cerr << "Time : " << (double)clock() / (double)CLOCKS_PER_SEC << "s\n";
  return 0;
}
