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 <class T>
struct Dijkstra {
  const T inf = numeric_limits<T>::max() / 2 - 1;
  vector<T> dist;
  Dijkstra() {}
  Dijkstra(int n) { resize(n); }
  void resize(int n) {
    g.resize(n);
    dist.resize(n);
    used.resize(n);
  }
  void add_edge(int a, int b, T c) { g[a].emplace_back(c, b); }
  void get_distance(int a) {
    priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>>
        pq;
    fill(dist.begin(), dist.end(), inf);
    fill(used.begin(), used.end(), false);
    pq.push(make_pair(0, a));
    while (!pq.empty()) {
      T d;
      int t;
      tie(d, t) = pq.top();
      pq.pop();
      if (used[t]) continue;
      used[t] = true;
      dist[t] = d;
      for (auto e : g[t]) {
        if (dist[e.second] <= (d + e.first)) continue;
        pq.push(make_pair(d + e.first, e.second));
      }
    }
  }

 private:
  vector<vector<pair<int, T>>> g;
  vector<bool> used;
};
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long n, x;
  cin >> n >> x;
  vector<long long> a(n);
  for (long long i = 0, i_len = (n); i < i_len; i++) cin >> a[i];
  Dijkstra<long long> di(n + 1);
  for (long long i = 0, i_len = (n); i < i_len; i++) {
    di.add_edge(0, i + 1, a[i]);
    di.add_edge(i + 1, (i + 1) % n + 1, x);
  }
  di.get_distance(0);
  vector<pair<long long, long long>> from(
      n, make_pair(LONG_LONG_MAX, LONG_LONG_MAX));
  long long mc = 0;
  for (long long i = 0, i_len = (n); i < i_len; i++) {
    long long dist = di.dist[i + 1];
    for (long long ii = 0, ii_len = (n); ii < ii_len; ii++) {
      if (dist < a[ii]) continue;
      if ((dist - a[ii]) % x != 0) continue;
      long long cnt = (dist - a[ii]) / x;
      if (cnt < from[i].first) {
        from[i].first = cnt;
        from[i].second = a[ii];
      }
    }
    mc = max(mc, from[i].first);
  }
  long long ans = mc * x;
  for (long long i = 0, i_len = (n); i < i_len; i++) ans += from[i].second;
  cout << ans << endl;
  return 0;
}
