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 = (1 << 30);
const long long INFLL = 1LL << 62;
const long double EPS = 1e-12;
template <typename T>
void vec_print(vector<T> VEC) {
  for (int i = (0); i < (VEC.size()); ++i) {
    cout << VEC[i] << " ";
  }
  cout << "\n";
};
template <typename T>
void mat_print(vector<vector<T> > MAT) {
  for (int i = (0); i < (MAT.size()); ++i) {
    for (int j = (0); j < (MAT[i].size()); ++j) {
      cout << MAT[i][j] << " ";
    }
    cout << "\n";
  }
};
class HOGE {
 public:
  long long index;
  long long value;
  HOGE(long long index, long long value) {
    this->index = index;
    this->value = value;
  };
  ~HOGE(void) { return; };
  void print(void) {
    cout << "index : " << index << ", value : " << value << "\n";
    return;
  };
  bool operator==(const HOGE &obj) { return (this->value == obj.value); };
  bool operator<(const HOGE &obj) { return (this->value < obj.value); };
  bool operator>(const HOGE &obj) { return (this->value > obj.value); };
};
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long N, x;
  cin >> N >> x;
  vector<long long> a(N);
  for (int i = (0); i < (N); ++i) {
    cin >> a[i];
  }
  long long delta_N;
  long long min_time;
  long long new_N;
  long long init = -1;
  delta_N = min(a[N - 1] / x, N - 1);
  min_time = a[N - 1];
  new_N = N - 1;
  for (int j = (1); j < (delta_N + 1); ++j) {
    new_N--;
    min_time = min(min_time, j * x + a[new_N]);
  }
  if (min_time == a[N - 1]) {
    init = N - 1;
  } else {
    a[N - 1] = 0;
  }
  for (int i = (0); i < (N - 1); ++i) {
    long long min_time = min(a[i], x + min_time);
    if (min_time == a[i]) {
      init = i;
    } else {
      a[i] = 0;
    }
  }
  long long A;
  long long count = 0;
  long long i_buf = 0;
  long long i_max = 0;
  for (int i = (init); i < (N + init); ++i) {
    long long i_tmp = i % N;
    if (a[i_tmp] > 0) {
      i_max = max(i_max, i_buf);
      A = a[i_tmp];
      count += A;
      i_buf = 0;
    } else {
      i_buf++;
      count += A;
    }
  }
  i_max = max(i_max, i_buf);
  count += x * i_max;
  cout << count << "\n";
  return 0;
}
