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 long long int LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
int N;
void build(vector<int> &segtree, int idx, int val) {
  int s = (int)(segtree).size() - (N - idx);
  segtree[s] = val;
  while (1) {
    if (s == 0) break;
    s = (s - 1) / 2;
    segtree[s] = min(segtree[s * 2 + 1], segtree[s * 2 + 2]);
  }
}
int _query(vector<int> &segtree, int a, int b, int idx, int l, int r) {
  if (a <= l && r <= b) return segtree[idx];
  if (r <= a || b <= l) return INF;
  int vector<long long int> =
      _query(segtree, a, b, idx * 2 + 1, l, (l + r) / 2);
  int rl = _query(segtree, a, b, idx * 2 + 2, (l + r) / 2, r);
  return min(vector<long long int>, rl);
}
int query(vector<int> &segtree, int l, int r) {
  return _query(segtree, l, r + 1, 0, 0, N);
}
int main() {
  int n, x;
  cin >> n >> x;
  vector<int> a(n);
  for (int i = 0; i < (n); ++i) {
    cin >> a[i];
  }
  N = 1;
  int len = 1;
  while (N < n) {
    N *= 2;
    len += N;
  }
  vector<int> segtree(len, INF);
  for (int i = 0; i < (n); ++i) {
    build(segtree, i, a[i]);
  }
  int ans = INF;
  for (int k = 0; k < (n); ++k) {
    int sum = 0;
    for (int i = 0; i < (n); ++i) {
      if (k + i >= n) {
        int l = i;
        int r = n - 1;
        int res = query(segtree, l, r);
        l = 0;
        r = (k + i) % n;
        res = min(res, query(segtree, l, r));
        sum += res;
      } else {
        sum += query(segtree, i, k + i);
      }
    }
    sum += x * k;
    ans = min(ans, sum);
  }
  cout << ans << endl;
  return 0;
}
