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 <typename T>
using lp_queue = priority_queue<T, vector<T>, greater<T>>;
static const long long INF = 1ll << 39;
struct Edge {
  int src;
  int dst;
  long long weight;
  Edge(void) {}
  Edge(int s, int d, long long w) {
    src = s;
    dst = d;
    weight = w;
  }
};
bool operator<(const Edge &e, const Edge &f) {
  if (e.weight != f.weight) {
    return e.weight > f.weight;
  } else {
    return e.src != f.src ? e.src < f.src : e.dst < f.dst;
  }
}
void join(vector<vector<Edge>> &g, int s, int d, long long w = 1) {
  g[s].push_back(Edge(s, d, w));
  g[d].push_back(Edge(d, s, w));
}
void connect(vector<vector<Edge>> &g, int s, int d, long long w = 1) {
  g[s].push_back(Edge(s, d, w));
}
vector<long long> dijkstra(vector<vector<Edge>> &g, int s, vector<int> &prev) {
  lp_queue<pair<long long, int>> q;
  int V = g.size();
  vector<long long> d(V, INF);
  d[s] = 0;
  q.push(pair<long long, int>(0, s));
  while (!q.empty()) {
    pair<long long, int> p = q.top();
    q.pop();
    int v = p.second;
    if (d[v] < p.first) continue;
    for (Edge &e : g[v])
      if (d[e.dst] > d[v] + e.weight) {
        d[e.dst] = d[v] + e.weight;
        q.push(pair<long long, int>(d[e.dst], e.dst));
        prev[e.dst] = v;
      }
  }
  return d;
}
int num_path(vector<int> &prev, int t) {
  int res = 0;
  for (; t; t = prev[t]) res++;
  return res;
}
int main(void) {
  int N;
  long long x;
  cin >> N >> x;
  vector<vector<Edge>> g(N + 1);
  int i;
  vector<long long> a(N);
  for (i = 0; i < N; i++) {
    scanf("%lld", &a[i]);
    connect(g, 0, i + 1, a[i]);
    connect(g, i + 1, (i + 1) % N + 1, x);
  }
  vector<int> prev(N + 1);
  vector<long long> mincost = dijkstra(g, 0, prev);
  long long res = 0;
  long long magic = 0;
  for (i = 1; i <= N; i++) {
    res += mincost[i];
    int n = num_path(prev, i) - 1;
    if (n > magic) {
      magic = n;
    }
  }
  cout << res - max(0ll, magic - 1) * x << endl;
  return 0;
}
