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...);
}
using T = long long;
bool QUERY;
struct Line {
  mutable T a, b, p;
  T Eval(T x) const { return a * x + b; }
  bool operator<(const Line& o) const { return QUERY ? p < o.p : a < o.a; }
};
struct ConvexHull : multiset<Line> {
  const T kInf = numeric_limits<T>::max();
  T div(T a, T b) { return a / b - ((a ^ b) < 0 && a % b); }
  bool isect(iterator x, iterator y) {
    if (y == end()) {
      x->p = kInf;
      return false;
    }
    if (x->a == y->a) {
      x->p = x->b > y->b ? kInf : -kInf;
    } else {
      x->p = div(y->b - x->b, x->a - y->a);
    }
    return x->p >= y->p;
  }
  void InsertLine(T a, T b) {
    a *= -1, b *= -1;
    auto nx = insert({a, b, 0}), it = nx++, pv = it;
    while (isect(it, nx)) {
      nx = erase(nx);
    }
    if (pv != begin() && isect(--pv, it)) {
      isect(pv, it = erase(it));
    }
    while ((it = pv) != begin() && (--pv)->p >= it->p) {
      isect(pv, erase(it));
    }
  }
  T EvalMax(T x) {
    if (empty()) {
      return -2e18;
    }
    QUERY = 1;
    auto it = lower_bound({0, 0, x});
    QUERY = 0;
    return it->Eval(x);
  }
} CH;
long long solve(vector<long long> A, long long x) {
  int N = A.size();
  vector<long long> DP(N);
  DP[0] = A[0];
  CH.clear();
  CH.InsertLine(A[0] + x, A[0]);
  for (int i = 0; i < N; i++) {
    DP[i] = -CH.EvalMax(i);
    if (i < N - 1) {
      CH.InsertLine(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;
}
