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>
std::string Name = "<stdin>";
std::string iput = Name.substr(0, Name.length() - 4) + ".in";
std::string oput = Name.substr(0, Name.length() - 4) + ".out";
template <class T>
inline bool chkmin(T &x, T y) {
  return x > y ? x = y, true : false;
}
template <class T>
inline bool chkmax(T &x, T y) {
  return x < y ? x = y, true : false;
}
template <class T>
inline T &read(T &x) {
  static int f;
  static char c;
  for (f = 1; !isdigit(c = getchar_unlocked());) {
    if (c == '-') f = -1;
  }
  for (x = 0; isdigit(c); c = getchar_unlocked()) {
    x = x * 10 + c - 48;
  }
  return x *= f;
}
template <class T>
inline void write(T x, const char p = '\n') {
  static int top;
  static int s[30];
  if (x < 0) {
    x = -x;
    putchar_unlocked('-');
  }
  do s[++top] = x % 10 + 48;
  while (x /= 10);
  while (top) putchar_unlocked(s[top--]);
  putchar_unlocked(p);
}
const int maxn = 1e5 + 5;
int n;
int x;
int a[maxn];
void exec() {
  read(n);
  read(x);
  for (int i = 1; i <= n; ++i) read(a[i]);
  long long ans = 1e18;
  for (int i = 0; i < n; ++i) {
    long long now = i * x;
    static std::pair<int, int> q[maxn];
    int front = 1, rear = 0;
    for (int j = n + 1 - i; j <= n; ++j) {
      while (front <= rear && q[rear].first >= a[j]) --rear;
      q[++rear] = std::pair<int, int>(a[j], j - n);
    }
    for (int j = 1; j <= n; ++j) {
      while (front <= rear && q[front].second < j - i) ++front;
      while (front <= rear && q[rear].first >= a[j]) --rear;
      q[++rear] = std::pair<int, int>(a[j], j);
      now += q[front].first;
    }
    chkmin(ans, now);
  }
  write(ans);
}
int main() {
  if (fopen(iput.c_str(), "r") != NULL) {
    freopen(iput.c_str(), "r", stdin);
    freopen(oput.c_str(), "w", stdout);
  }
  exec();
  fclose(stdin);
  fclose(stdout);
  return 0;
}
