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;
template <class T>
void print(const T &value) {
  std::cout << value << std::endl;
}
void yesno(bool a) {
  if (a)
    cout << "yes" << endl;
  else
    cout << "no" << endl;
}
void YesNo(bool a) {
  if (a)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}
void YESNO(bool a) {
  if (a)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}
template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
long long INF = 10000000;
long long mod = 1000000007;
int dx[8] = {-1, 0, 0, 1, -1, -1, 1, 1};
int dy[8] = {0, -1, 1, 0, -1, 1, -1, 1};
using Graph = vector<vector<int>>;
using GraphW = vector<vector<pair<int, int>>>;
using P = pair<int, int>;
using lP = pair<long long, long long>;
using PP = pair<int, P>;
using p_queue = priority_queue<int, vector<int>, greater<int>>;
class UnionFindTree {
 public:
  UnionFindTree(int size) : memberSize(size) {
    par.resize(size * sizeof(long long));
    rnk.resize(size * sizeof(long long));
    diff_weight.resize(size * sizeof(long long));
    for (int i = 0; i < size; i++) {
      par[i] = i;
      rnk[i] = 0;
      diff_weight[i] = 0;
    }
  }
  int memberSize;
  vector<int> par;
  vector<int> rnk;
  vector<long long> diff_weight;
  void init(long long n) {
    for (int i = 0; i < n; i++) {
      par[i] = i;
      rnk[i] = 1;
    }
  }
  int find(long long x) {
    if (par[x] == x) {
      return x;
    } else {
      int r = find(par[x]);
      diff_weight[x] += diff_weight[par[x]];
      return par[x] = r;
    }
  }
  bool same(long long x, long long y) { return find(x) == find(y); }
  void unite(long long x, long long y) {
    x = find(x);
    y = find(y);
    if (x == y) {
      return;
    }
    if (rnk[x] < rnk[y]) {
      par[x] = y;
    } else {
      par[y] = x;
      if (rnk[x] == rnk[y]) {
        rnk[x]++;
      }
    }
  }
  long long weight(long long x) {
    find(x);
    return diff_weight[x];
  }
  long long diff(long long x, long long y) { return weight(y) - weight(x); }
  void merge(int x, int y, int w) {
    w += weight(x);
    w -= weight(y);
    x = find(x);
    y = find(y);
    if (x == y) {
      return;
    }
    if (rnk[x] < rnk[y]) {
      par[x] = y;
      diff_weight[x] = -w;
    } else {
      par[y] = x;
      diff_weight[y] = w;
      if (rnk[x] == rnk[y]) {
        rnk[x]++;
      }
    }
  }
};
int main() {
  long long N, x;
  cin >> N >> x;
  long long a[N + 1][N + 1];
  for (int i = 0; i < N; i++) {
    cin >> a[0][i];
    int j = i + 1;
    for (int k = 1; k < N - 1 + 1; k++) {
      long long tmp = j == 0 ? a[k - 1][N] : a[k - 1][j - 1];
      if (j == N) {
        j = 0;
      }
      a[k][j] = tmp + x;
      j++;
    }
  }
  long long magic = 0;
  for (int i = 0; i < N; i++) {
    long long cost = a[0][i];
    for (int j = 0; j < N; j++) {
      if (cost > a[j][i]) {
        if (magic < j) {
          magic = j;
        }
      }
    }
  }
  long long ans = 0;
  for (int i = 0; i < N; i++) {
    long long cost = a[0][i];
    long long mg = 0;
    for (int j = 0; j < N; j++) {
      if (cost > a[j][i]) {
        mg = j;
        cost = a[j][i];
      }
    }
    if (mg != magic) {
      cost -= mg * x;
    }
    ans += cost;
  }
  print(ans);
}
