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 int INF = (0x7FFFFFFFL);
const long long INFF = (0x7FFFFFFFFFFFFFFFL);
const int MOD = 1e9 + 7;
const int MODD = 998244353;
const double PI = acos(-1.0);
const double EPS = 1e-9;
int dx[9] = {1, 0, -1, 0, 1, -1, -1, 1, 0};
int dy[9] = {0, 1, 0, -1, -1, -1, 1, 1, 0};
template <typename T>
void MACRO_VAR_Scan(T &t) {
  cin >> t;
}
template <typename First, typename... Rest>
void MACRO_VAR_Scan(First &first, Rest &...rest) {
  cin >> first;
  MACRO_VAR_Scan(rest...);
}
template <class T>
ostream &operator<<(ostream &o, const vector<T> &j) {
  o << "{";
  for (int i = 0; i < (int)j.size(); ++i) o << (i > 0 ? ", " : "") << j[i];
  o << "}";
  return o;
}
template <class T, class U>
ostream &operator<<(ostream &o, const pair<T, U> &j) {
  o << "{" << j.first << ", " << j.second << "}";
  return o;
}
template <class T, class U>
ostream &operator<<(ostream &o, const map<T, U> &j) {
  o << "{";
  for (auto t = j.begin(); t != j.end(); ++t)
    o << (t != j.begin() ? ", " : "") << *t;
  o << "}";
  return o;
}
template <class T>
ostream &operator<<(ostream &o, const set<T> &j) {
  o << "{";
  for (auto t = j.begin(); t != j.end(); ++t)
    o << (t != j.begin() ? ", " : "") << *t;
  o << "}";
  return o;
}
inline void print(void) { cout << endl; }
template <class Head>
void print(Head &&head) {
  cout << head;
  print();
}
template <class Head, class... Tail>
void print(Head &&head, Tail &&...tail) {
  cout << head << " ";
  print(forward<Tail>(tail)...);
}
template <typename T>
void PA(T &a) {
  int ASIZE = sizeof(a) / sizeof(a[0]);
  for (int ii = 0; ii < ASIZE; ++ii) {
    cout << a[ii] << " \n"[ii == ASIZE - 1];
  }
}
template <typename T>
void PV(T &v) {
  int VSIZE = v.size();
  for (int ii = 0; ii < VSIZE; ++ii) {
    cout << v[ii] << " \n"[ii == VSIZE - 1];
  }
}
inline void YES(bool x) { cout << ((x) ? "YES" : "NO") << endl; }
inline void Yes(bool x) { cout << ((x) ? "Yes" : "No") << endl; }
inline void yes(bool x) { cout << ((x) ? "yes" : "no") << endl; }
inline void yES(bool x) { cout << ((x) ? "yES" : "nO") << endl; }
inline void Yay(bool x) { cout << ((x) ? "Yay!" : ":(") << endl; }
inline void sankou(bool x, string a, string b) {
  cout << ((x) ? (a) : (b)) << endl;
}
inline long long MOP(long long x, long long n, long long m = MOD) {
  long long r = 1;
  while (n > 0) {
    if (n & 1) (r *= x) %= m;
    (x *= x) %= m;
    n >>= 1;
  }
  return r;
}
inline long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : 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 = 1ll;
  do {
    if (b & 1) c *= 1ll * a;
    a *= 1ll * a;
  } while (b >>= 1);
  return c;
}
template <typename T>
inline bool between(T x, T a, T b) {
  return ((a <= x) && (x < b));
}
template <class T>
inline T sqr(T x) {
  return x * x;
}
template <typename A, typename B>
inline bool chmax(A &a, const B &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename A, typename B>
inline bool chmin(A &a, const B &b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
struct abracadabra {
  abracadabra() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
  };
} ABRACADABRA;
int N, X;
int change(int from, int to) {
  if (from <= to)
    return (to - from) * X;
  else
    return (to - from + N) * X;
}
signed main() {
  cin >> N >> X;
  vector<int> A(N);
  for (auto &i : A) cin >> i;
  ;
  vector<int> B(N);
  for (long long i = long long(0); i < long long(N); ++i) B[i] = A[i];
  long long res = 0;
  long long max = 0;
  for (long long i = long long(0); i < long long(N); ++i) {
    long long min = 0;
    for (long long j = long long(0); j < long long(N); ++j) {
      if (B[i] >= A[j] + change(j, i)) {
        B[i] = A[j] + change(j, i);
        min = A[j];
        chmax(max, change(j, i));
      }
    }
    res += min;
  }
  print(res + max);
}
