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;
long long low(vector<long long> a, long long b) {
  decltype(a)::iterator c = lower_bound(a.begin(), a.end(), b);
  long long d = c - a.begin();
  return d;
}
long long upp(vector<long long> a, long long b) {
  decltype(a)::iterator c = upper_bound(a.begin(), a.end(), b);
  long long d = c - a.begin();
  return d;
}
template <class T>
void cou(vector<vector<T>> a) {
  long long b = a.size();
  long long c = a[0].size();
  for (long long i = 0; i < b; i++) {
    for (long long j = 0; j < c; j++) {
      cout << a[i][j];
      if (j == c - 1)
        cout << endl;
      else
        cout << ' ';
    }
  }
}
long long wari(long long a, long long b) {
  if (a % b == 0)
    return a / b;
  else
    return a / b + 1;
}
long long keta(long long a) {
  long double b = a;
  b = log10(b);
  long long c = b;
  return c + 1;
}
long long souwa(long long a) { return a * (a + 1) / 2; }
long long gcm(long long a, long long b) {
  if (a % b == 0) return b;
  return gcm(b, a % b);
}
bool prime(long long a) {
  if (a < 2)
    return false;
  else if (a == 2)
    return true;
  else if (a % 2 == 0)
    return false;
  long double b = sqrt(a);
  for (long long i = 3; i <= b; i += 2) {
    if (a % i == 0) {
      return false;
    }
  }
  return true;
}
struct Union {
  vector<long long> par;
  Union(long long a) { par = vector<long long>(a, -1); }
  long long find(long long a) {
    if (par[a] < 0)
      return a;
    else
      return par[a] = find(par[a]);
  }
  bool same(long long a, long long b) { return find(a) == find(b); }
  long long Size(long long a) { return -par[find(a)]; }
  void unite(long long a, long long b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (Size(b) > Size(a)) swap<long long>(a, b);
    par[a] += par[b];
    par[b] = a;
  }
};
long long ketas(long long a) {
  string b = to_string(a);
  long long c = 0;
  for (long long i = 0; i < keta(a); i++) {
    c += b[i] - '0';
  }
  return c;
}
long long lcm(long long a, long long b) { return a / gcm(a, b) * b; }
bool fe(long long a, long long b) {
  a %= 10;
  b %= 10;
  if (a == 0) a = 10;
  if (b == 0) b = 10;
  if (a > b)
    return true;
  else
    return false;
}
long long INF = 1000000007;
struct edge {
  long long s, t, d;
};
vector<long long> mojisyu(string a) {
  vector<long long> b(26, 0);
  for (long long i = 0; i < a.size(); i++) {
    b[a[i] - 'a']++;
  }
  return b;
}
long long wa2(long long a) {
  if (a % 2 == 1) return a / 2;
  return a / 2 - 1;
}
signed main() {
  long long a, b;
  cin >> a >> b;
  vector<long long> c(a);
  for (long long i = 0; i < a; i++) cin >> c[i];
  for (long long i = 0; i < a; i++) {
    for (long long j = 0; j < a + 1; j++) {
      c[(i + j) % a] = min(c[(i + j) % a], c[i] + b * j);
    }
  }
  long long d = 0;
  for (long long i = 0; i < a; i++) d += c[i];
  cout << d << endl;
}
