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 = 1e9, MOD = 1e9 + 7,
          around[] = {0, 1, 1, -1, -1, 0, -1, 1, 0, 0};
const int vx[] = {1, 0, -1, 0}, vy[] = {0, 1, 0, -1};
const int sqrtN = 512;
const long long LINF = 1e18;
const long double PI = abs(acos(-1));
int a[2010];
struct Node {
  int data;
  Node(int data) : data(data){};
  Node operator*(const Node r) const { return data < r.data ? *this : r; }
} e(INF);
struct SegmentTree {
  vector<Node> seg;
  int sz = 1;
  SegmentTree(int n) {
    while (sz < n) sz *= 2;
    seg.assign(sz * 2, e);
  }
  void update(int k, int x) {
    k += sz - 1;
    seg[k] = Node(x);
    while (k) {
      k = (k - 1) / 2;
      seg[k] = seg[2 * k + 1] * seg[2 * k + 2];
    }
  }
  int get(int a, int b) { return _get(a, b, 0, 0, sz).data; }
  Node _get(int a, int b, int k, int l, int r) {
    if (b <= l || r <= a) return e;
    if (a <= l && r <= b) return seg[k];
    return _get(a, b, 2 * k + 1, l, (l + r) / 2) *
           _get(a, b, 2 * k + 2, (l + r) / 2, r);
  }
  int val(int k) { return seg[k + sz - 1].data; }
};
int main() {
  int n, t;
  cin >> n >> t;
  for (int i = (0); i < (n); i++) cin >> a[i];
  SegmentTree seg(n);
  for (int i = (0); i < (n); i++) seg.update(i, a[i]);
  for (int i = (0); i < (n); i++) cout << seg.val(i) << " ";
  cout << endl;
  long long mi = LINF;
  for (int i = (0); i < (n); i++) {
    long long sum = i * t;
    for (int j = (0); j < (n); j++) {
      sum += min(seg.get(max(0, j - i), j + 1), seg.get(min(n, j - i + n), n));
    }
    mi = min(mi, sum);
  }
  cout << mi << endl;
  return 0;
}
