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 P, typename Q>
ostream& operator<<(ostream& os, pair<P, Q> p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
struct E {
  int src, dst, cost, cap, rev;
  E(int _src, int _dst, int _cost, int _cap, int _rev)
      : src(_src), dst(_dst), cost(_cost), cap(_cap), rev(_rev) {}
};
const int V = 2000 + 5;
vector<E> g[V];
int cost[V], h[V], prevv[V], preve[V];
const int inf = (1 << 28);
void add_edge(int src, int dst, int cost, int cap) {
  g[src].push_back(E(src, dst, cost, cap, (int)g[dst].size()));
  g[dst].push_back(E(dst, src, -cost, 0, (int)g[src].size() - 1));
  return;
}
int min_cost_flow(int src, int snk, int req) {
  int ret = 0;
  fill(h, h + V, 0);
  while (0 < req) {
    priority_queue<pair<int, int>> q;
    fill(cost, cost + V, inf);
    cost[src] = 0;
    for (q.push(make_pair(-0, src)); q.size();) {
      pair<int, int> p = q.top();
      q.pop();
      int v = p.second;
      int c = -p.first;
      if (cost[v] < c) continue;
      for (int i = 0; i < g[v].size(); ++i) {
        E& e = g[v][i];
        int d = cost[v] + e.cost + h[e.src] - h[e.dst];
        if (0 < e.cap && d < cost[e.dst]) {
          cost[e.dst] = d;
          prevv[e.dst] = v;
          preve[e.dst] = i;
          q.push(make_pair(-cost[e.dst], e.dst));
        }
      }
    }
    if (cost[snk] == inf) break;
    for (int i = 0; i < V; ++i) {
      h[i] += cost[i];
    }
    int d = req;
    for (int v = snk; v != src; v = prevv[v]) {
      d = min(d, g[prevv[v]][preve[v]].cap);
    }
    req -= d;
    ret += d * h[snk];
    for (int v = snk; v != src; v = prevv[v]) {
      E& e = g[prevv[v]][preve[v]];
      e.cap -= d;
      g[v][e.rev].cap += d;
    }
  }
  return ret;
}
int main(int argc, char* argv[]) {
  int n, x;
  while (cin >> n >> x) {
    fill(g, g + V, vector<E>());
    long long int a[n];
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
    }
    auto enchant = [&](int i, int j) { return (((j + n) - i) % n) * x; };
    const int src = n + 1;
    const int snk = n + 2;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        add_edge(i, j, enchant(i, j), 1);
      }
    }
    for (int i = 0; i < n; ++i) {
      add_edge(src, i, a[i], 1 << 29);
    }
    for (int i = 0; i < n; ++i) {
      add_edge(i, snk, 0, 1);
    }
    cout << min_cost_flow(src, snk, 1 << 29) << endl;
  }
  return 0;
}
